F. Sort hacking
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard 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.

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