CF1252F.Regular Forestation

A forestation is an act of planting a bunch of trees to grow a forest, usually to replace a forest that had been cut down. Strangely enough, graph theorists have another idea on how to make a forest, i.e. 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$ which degree is at least $2$ (i.e. directly connected to at least $2$ other nodes in $U$ ). If we remove $u$ from $U$ , then we will get two or more disconnected (smaller) trees, or also known as forest by graph theorists. In this problem, we are going to investigate a special forestation of a tree done by graph theorists.

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

We call a node $u$ in a tree $U$ as a good cutting point if and only if the removal of $u$ from $U$ causes two or more disconnected trees, and all those disconnected trees are pairwise identical.

Given a tree $U$ , your task is to determine whether there exists a good cutting point in $U$ . If there is such a node, then you should 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.

There is exactly one good cutting point in this tree, i.e. node $4$ . Observe that by removing node $4$ , we will get three identical trees (in this case, line graphs), i.e. $\{5, 1, 7, 13\}$ , $\{8, 2, 11, 6\}$ , and $\{3, 12, 9, 10\}$ , which are denoted by $A$ , $B$ , and $C$ respectively in the figure.

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

Of course, there exists other bijection functions for those trees.

Input begins with a line containting an integer: $N$ ( $3 \le N \le 4000$ ) representing the number of nodes in the given tree. The next $N - 1$ lines each contains two integers: $a_i$ $b_i$ ( $1 \le a_i < b_i \le N$ ) representing an edge $(a_i,b_i)$ in the given tree. It is guaranteed that any two nodes in the given tree are connected to each other by a sequence of edges.

Output in a line an integer representing the maximum number of disconnected trees that can be obtained by removing exactly one good cutting point, or output -1 if there is no such good cutting point.

Explanation for the sample input/output #1

This is the example from the problem description.