## CCO '03 P4 - Constrained Permutations

View as PDF

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

Problem type
##### 2003 Canadian Computing Competition, Stage 2

A permutation on the numbers is a linear ordering of the numbers. For example, there are permutations of the numbers . They are , , , , and . Another way to think of it is removing disks numbered to 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 permutations of the numbers . We call this " factorial."

For this problem, you will be given an integer and a series of constraints on the ordering of the numbers. That is, you will be given pairs indicating that must come before in the permutation.

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

#### Input Specification

Your input will be lines. The first line will contain the number . The second line will contain the integer , indicating the number of constraints. The remaining lines will be pairs of distinct integers which are in the range .

#### Output Specification

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