### 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)

Bobon Jan 04, 2009 - 3:57:08 pm UTC are the constraints guaranteed to be in the range?hansonw1on Jan 04, 2009 - 4:26:56 pm UTC Re: are the constraints guaranteed to be in the range?