Canadian Computing Competition: 2003 Stage 2, Day 2, Problem 1

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