Counting Hamiltonian Cycles in a Growing Neural Network

A Martian’s neural network starts as a forest of m undirected trees \(T_1(V_1, E_1), T_2(V_2, E_2), \ldots, T_m(V_m, E_m)\). As the Martian ages, new neural connections grow. Initially, the extra edge set \(E^*\) is empty. Then, the network evolves by connecting every pair of nodes belonging to different trees, i.e. if \(u \in V_i\) and \(v \in V_j\) with \(i \neq j\), then the edge \((u,v)\) is added to \(E^*\).

After no more connections can grow, the resulting graph is defined as \[ G(V,E) \quad \text{where} \quad V = V_1 \cup V_2 \cup \cdots \cup V_m, \quad E = E_1 \cup E_2 \cup \cdots \cup E_m \cup E^*. \]

A Hamiltonian cycle in \(G\) is a simple cycle that starts at the first node of the first tree (denoted as \(T_1\)'s first vertex), visits every other vertex exactly once and returns to the starting vertex. Note that an edge between two vertices is present if:

• The two vertices belong to different trees (since all such connections exist), or
• The two vertices belong to the same tree and there is an edge in that tree (given in the input).

Your task is to compute the number of Hamiltonian cycles in \(G\).

Input/Output details: See below.

inputFormat

The input begins with an integer \(m\) indicating the number of trees in the forest. Then for each tree, the input is given as follows:

• An integer \(n_i\) representing the number of nodes in the \(i\)-th tree. The nodes in each tree are numbered from 1 to \(n_i\).
• Followed by \(n_i - 1\) lines, each containing two integers \(u\) and \(v\) (\(1 \le u,v \le n_i\)) describing an edge in the tree.

The designated start vertex is \(1\) of the first tree (i.e. the first node of \(T_1\)).

outputFormat

Output a single integer that denotes the number of Hamiltonian cycles in \(G\), where a valid cycle is a simple cycle starting and ending at the starting vertex and visiting every vertex exactly once.

sample

1
3
1 2
2 3

0