2003 Canadian Computing Competition, Stage 2

Day 2, Problem 1: Constrained Permutations

A permutation on the numbers 1,2,...,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·(n-1) · · · 3·2·1 permutations of the numbers 1,...,n. We call this "n factorial."

For this problem, you will be given an integer n (1 ≤ n ≤ 9) and a series of k (k ≥ 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

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,...,n.

Output

Your output will be one integer, indicating the number of permutations of 1,...,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

All Submissions
Best Solutions


Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Dec 28, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)