Loopy transit

Time limit2sMemory limit256 MB

Summary

Count distinct directed simple cycles in a graph of up to 9 stations, treating rotations of a loop as one.

Level: Medium6 of 10
Topics: Graph, Backtracking, Brute force
Solved: No attempts yet

Problem

Luke likes riding public transit in the cities he visits, just for fun. What he enjoys most is finding loops: he leaves one station, travels along the connections through at least one other station, and comes back to the station he started from. He wants to know how many such loops each transit system has.

What Luke counts is simple loops. A simple loop is a sequence of distinct stations $t_1, t_2, \dots, t_j$ such that there is a direct connection from $t_i$ to $t_{i+1}$ for every $i$ with $1 \le i < j$ , and a direct connection from $t_j$ to $t_1$ as well. A loop can be written down starting from any of its stations, so every cyclic shift of such a sequence is the same simple loop. Two simple loops that visit the same set of stations in a different order are counted as different loops.

Write a program that counts the distinct simple loops in the transit system.

Input

The first line contains the number of stations $m$ in the transit system ( $3 \le m \le 9$ ). Stations are numbered $0$ to $m-1$ .

The second line contains the number of connections $n$ ( $1 \le n \le m(m-1)$ ). Each of the next $n$ lines describes one connection as two integers $s$ and $t$ ( $0 \le s < m$ , $0 \le t < m$ , $s \ne t$ ), meaning there is a one-way connection from station $s$ to station $t$ .

Output

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

Examples3

Example 1
Input
```
5
5
0 1
1 2
2 3
3 4
4 2
```
Expected output
```
1
```

Example 2

Input

Expected output

Example 3
Input
```
4
8
0 1
1 2
2 3
3 0
1 0
2 1
3 2
0 3
```
Expected output
```
6
```