405864: GYM102136 F Sort hacking

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Sort hackingtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Vova claims that he came up with a new kind of sorting algorithm. His algorithm differs in that it can sort, according to Vova, any permutation of length N while doing the same comparisons for any permutation. In total, it makes M comparisons, where the i-th comparison occurs over the numbers at positions xi and yi respectively. If at the time of comparison the number at the position xi turned out to be larger, then he swaps them.

Vanya was skeptical about the discovery of Vova. He is sure that there will be such permutations that Vova's sort can not order in ascending order. Help Vanya determine the number of such permutations.

Input

The first line contains two integers N and M — the size of the permutation and the number of comparisons in the Vova's sort.

The following M lines contain comparisons. The i-th row contains two integers xi and yi — the positions of the compared elements.

1 ≤ N ≤ 15
1 ≤ M ≤ 200
1 ≤ xi, yi ≤ N
Output

In a single line output one integer — the number of permutations that Vova's sort can not order in ascending order.

ExamplesInput
3 3
1 2
2 3
1 3
Output
2
Input
2 1
1 2
Output
0
Input
2 1
2 1
Output
2
Note

In the first test case, the following permutations are suitable: [3, 2, 1], [2, 3, 1].

In the second test case, the following permutations are suitable: [1, 2], [2, 1].

加入题单

上一题 下一题 算法标签: