405864: GYM102136 F Sort hacking

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 x_i and y_i respectively. If at the time of comparison the number at the position x_i 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.

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 x_i and y_i — 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.

3 3
1 2
2 3
1 3

2

2 1
1 2

0

2 1
2 1

2

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].