Problem D
Cubic Cycle

Consider an undirected graph $G$ with vertices $V$ and edges $E$. A Hamiltonian Cycle is a subset of edges $C \subseteq E$ such that every vertex in $v$ is the endpoint of precisely two edges in $C$ and the graph $H$ with vertices $V$ and edges $C$ is connected. In simpler terms, the edges of $C$ form a single cycle that includes all vertices.

Hamiltonian cycles are beautiful objects, but can be hard to find. Your most recent homework assignment in your Graph Theory course has given you the task of finding a Hamiltonian cycle in a particular graph $G$ (or determine if one exists). The graph itself is also beautiful, each vertex in $G$ is the endpoint of precisely three edges.

But it feels unfair to produce only one Hamiltonian cycle. All Hamiltonian cycles deserve recognition! So, you decided that you will in fact produce all Hamiltonian cycles in your homework solution.

Your task is to count the number of Hamiltonian cycles you will have to produce in your homework solution.

Figure 1: Illustration of the three Hamiltonian cycles in the first sample input. The cycles are depicted with thick edges.

Input

The first line contains a single even integer $N$ ($4 \leq N \leq 50$) giving the number of nodes.

Then $3 \cdot N / 2$ lines follow, each containing two integers $u, v$ ($0 \leq u < N, 0 \leq v < N, u \neq v$) describing an edge connecting vertex $u$ to vertex $v$. You are guaranteed any pair of nodes is connected by at most one edge and that each node is the endpoint of precisely three edges in the input.

Output

Display a single line with a single integer indicating the number of Hamiltonian cycles in the given graph.

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

3

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

6