Essential Treasure Burying

Carmen and his friends recently discovered a treasure chest. They plan to bury the treasure at one of the nodes in a highway network. The network has N nodes and N bidirectional roads. Every node is connected by at least one road, and no node has more than 4 incident roads. However, Carmen will not bury the treasure at any node with exactly 4 incident roads (since such nodes are very busy and might expose the treasure).

After drawing the map of the highway network, Carmen marks a node where he plans to bury the treasure with a cross. In order to investigate the best hiding strategy, he drew all possible scenarios. Two maps are considered essentially the same if and only if:

• The treasure burial locations correspond to each other;
• If there is a road between any two nodes, then in the corresponding map there is also a road between the corresponding nodes;
• If there is no road between any two nodes, then in the corresponding map there is also no road between the corresponding nodes.

Formally, let the highway network be represented by a graph with N nodes and N edges. The graph is connected and every node has degree at least 1 and at most 4. Only nodes with degree other than 4 are eligible for burying the treasure. Two burying schemes (i.e. a choice of an eligible node) are considered equivalent if there exists a graph isomorphism (a bijection from the set of nodes to itself) that maps the treasure node in one scheme to the treasure node in the other scheme while preserving adjacency relations.

Your task is to calculate the number of essentially different treasure burying schemes.

Note on formulae: All mathematical formulae are to be written in LaTeX format. For example, the number of nodes should be denoted as \(N\) and so on.

inputFormat

The first line contains an integer \(N\) (the number of nodes). Each of the next \(N\) lines contains two integers \(u\) and \(v\) (1-based indexing) which indicate that there is a bidirectional road between node \(u\) and node \(v\). It is guaranteed that the network is connected, has exactly \(N\) edges, and every node has degree at least 1 and at most 4.

outputFormat

Output a single integer: the number of essentially different treasure burying schemes, i.e. the number of orbits among the eligible nodes (nodes with degree \( eq 4\)) under the action of the automorphism group of the graph.

sample

4
1 2
2 3
3 4
4 1

1