Regular Forestation

Forestation is the act of planting many trees to grow a forest, usually to replace a forest that has been cut down. Graph theorists have another idea: make a forest by cutting down a tree. A tree is a graph of $N$ nodes connected by $N-1$ edges. Let $u$ be a node in a tree $U$ whose degree is at least 2, that is, $u$ is directly connected to at least 2 other nodes in $U$. If $u$ is removed from $U$, two or more smaller disconnected trees remain, which graph theorists call a forest.

Let $V(S)$ be the set of nodes in a tree $S$ and $V(T)$ be the set of nodes in a tree $T$. Trees $S$ and $T$ are identical if there exists a bijection $f: V(S) \to V(T)$ such that for all pairs of nodes $(s_i, s_j)$ in $V(S)$, $s_i$ and $s_j$ are connected by an edge in $S$ if and only if $f(s_i)$ and $f(s_j)$ are connected by an edge in $T$. If $f(s) = t$, then node $s$ in $S$ corresponds to node $t$ in $T$.

A node $u$ in a tree $U$ is a good cutting point if removing $u$ from $U$ leaves two or more disconnected trees, and all of those trees are pairwise identical.

Given a tree $U$, determine whether it has a good cutting point. If it does, output the maximum number of disconnected trees that can be obtained by removing exactly one good cutting point.

For example, consider the following tree of 13 nodes.

This tree has exactly one good cutting point, node 4. Removing node 4 gives three identical trees, which are line graphs. Trees A, B, and C are formed by the node sets $\{5, 1, 7, 13\}$, $\{8, 2, 11, 6\}$, and $\{3, 12, 9, 10\}$, respectively.

• A bijection between A and B: $f(5)=8$, $f(1)=2$, $f(7)=11$, $f(13)=6$.
• A bijection between A and C: $f(5)=3$, $f(1)=12$, $f(7)=9$, $f(13)=10$.
• A bijection between B and C: $f(8)=3$, $f(2)=12$, $f(11)=9$, $f(6)=10$.

Other bijections also exist.

The first line contains an integer $N$ ($3 \le N \le 4000$), the number of nodes in the tree. Each of the next $N-1$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i < b_i \le N$), representing an edge $(a_i, b_i)$ of the tree. Any two nodes in the tree are connected by a sequence of edges.

Print one integer on a line: the maximum number of disconnected trees that can be obtained by removing exactly one good cutting point. If there is no good cutting point, print $-1$.