CCO '03 P4 - Constrained Permutations

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 16M

Problem type
2003 Canadian Computing Competition, Stage 2

A permutation on the numbers 1, 2, \dots, n is a linear ordering of the numbers. For example, there are 6 permutations of the numbers 1, 2, 3. They are 123, 132, 213, 231, 312 and 321. Another way to think of it is removing n disks numbered 1 to n from a bag (without replacement) and recording the order in which they were drawn out.

Mathematicians (and other smart people) write down that there are n! = n \times (n-1) \dots 3 \times 2 \times 1 permutations of the numbers 1, \dots, n. We call this "n factorial."

For this problem, you will be given an integer n (1 \le n \le 9) and a series of k (k \ge 0) constraints on the ordering of the numbers. That is, you will be given k pairs (x,y) indicating that x must come before y in the permutation.

You are to output the number of permutations which satisfy all constraints.

Input Specification

Your input will be k + 2 lines. The first line will contain the number n. The second line will contain the integer k, indicating the number of constraints. The remaining k lines will be pairs of distinct integers which are in the range 1, \dots, n.

Output Specification

Your output will be one integer, indicating the number of permutations of 1, \dots, n which satisfy the k constraints.

Sample Input 1

3
2
1 2
2 3

Sample Output 1

1

Sample Input 2

4
2
1 2
2 1

Sample Output 2

0

Sample Input 3

4
2
1 2
2 3

Sample Output 3

4

Comments

There are no comments at the moment.