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