405864: GYM102136 F Sort hacking
Description
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.
InputThe 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.
In a single line output one integer — the number of permutations that Vova's sort can not order in ascending order.
ExamplesInput3 3Output
1 2
2 3
1 3
2Input
2 1Output
1 2
0Input
2 1Output
2 1
2Note
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].