Bajtazar became a fan of traveling around Byteotia over a year ago. In this country, there are $n$ cities connected by $m$ bidirectional roads. Bajtazar has taken a liking to non-trivial journeys. During these journeys, he starts from a certain city, moves along the Byteotian roads, and visits various cities of Byteotia, eventually returning to the starting city. The hero cannot visit any city twice during the journey (except for the starting one), nor can he use any connection twice.

All roads in Byteotia are black. Bajtazar did not like this, and during his next non-trivial journey, he will paint every traversed road canary yellow. In how many different ways can he paint the roads? Two colorings are considered different if there exists a road that has different colors in them.

Input

The first line of input contains two integers $n, m$ ($2 \le n \le 20$, $1 \le m \le \frac{n(n-1)}{2}$). The next $m$ lines each contain two natural numbers $u_i, v_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$), indicating that cities $u_i$ and $v_i$ are connected by a bidirectional road. No two cities are connected by more than one road.

Output

Output a single line containing one integer – the number of different possible road colorings that can be achieved.

Examples

Input 1

4 5
1 2
1 3
1 4
2 3
3 4

Output 1

3