Problem E
Loopy Transit

Luke likes to ride on public transit in different cities he visits, just for fun. He tries to find unique ways to travel in loops: leaving from one transit station, traveling along the transit connections to at least one other station, and returning to the station where he started. He is finding lots of loops, and he wants to know just how many there are in different transit systems. There may be so many he won’t ever have time to try them all, but he’ll find some satisfaction in knowing they are there.

He’s particularly interested in counting simple loops. A simple loop is a sequence of unique transit stations $t_1, t_2, \ldots , t_ j$, where there’s a way to connect directly from $t_ i$ to $t_{i+1}$ for $1 \leq i < j$ and also from $t_ j$ to $t_1$. Of course, we can write down a simple loop starting with of the stations in the loop, therefore we consider any cyclic shift of such a sequence to be the same simple loop. However, two simple loops which visit the same set of transit stations in a different order are considered distinct.

Help Luke by writing a program to count how many unique simple loops there are in each transit system. The following figures illustrate the transit stations (numbered ovals) and one-way connections (arrows) of the sample input.

Input

Input contains a description of one transit system. The description begins with a line containing an integer $3 \leq m \leq 9$ indicating the number of transit stations in the system. Stations are numbered $0$ to $m-1$. The next line contains an integer $1 \leq n \leq m(m-1)$ indicating the number of connections that follow, one connection per line. Each connection is a pair of integers $s~ t$ ($0 \leq s < m$, $0 \leq t < m$, $s \neq t$), indicating that there is a one-way connection from station $s$ to station $t$.

Output

Print the number of unique simple loops in the transit system.

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

1

8
10
0 1
1 2
2 3
3 4
4 5
5 0
2 6
6 0
3 7
7 0

3

4
8
0 1
1 2
2 3
3 0
1 0
2 1
3 2
0 3

6