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.

造林是指种植大量树木以形成森林，通常是为了替代被砍伐的森林。奇怪的是，图论学家对如何制造森林有另一种想法，即通过砍掉一棵树！

一棵树是由 $N$ 个节点和 $N - 1$ 条边构成的连通图。设 $u$ 是树 $U$ 中的一个节点，其度数至少为 $2$（即在 $U$ 中直接与至少 $2$ 个其他节点相连）。若从 $U$ 中移除 $u$，我们将得到两个或更多互不连通（更小的）树，图论学家也将这些不连通的树组成的集合称为“森林”。本题中，我们将研究图论学家所定义的一种特殊的“造林”操作——即对一棵树进行单点割裂。

设 $V(S)$ 表示树 $S$ 的节点集合，$V(T)$ 表示树 $T$ 的节点集合。当且仅当存在一个双射函数 $f : V(S) \rightarrow V(T)$，使得对任意节点对 $(s_i, s_j) \in V(S)$，$s_i$ 与 $s_j$ 在 $S$ 中由一条边相连，当且仅当 $f(s_i)$ 与 $f(s_j)$ 在 $T$ 中由一条边相连时，称树 $S$ 与树 $T$ 同构。注意：$f(s) = t$ 表示 $S$ 中的节点 $s$ 对应于 $T$ 中的节点 $t$。

我们称树 $U$ 中的一个节点 $u$ 为优质割点，当且仅当从 $U$ 中移除 $u$ 后，得到两个或更多互不连通的树，且这些不连通的树两两同构。

给定一棵树 $U$，你的任务是判断 $U$ 中是否存在优质割点。若存在，则输出恰好移除一个优质割点所能得到的最大不连通树的数量。

例如，考虑如下含 $13$ 个节点的树：

该树中恰有一个优质割点，即节点 $4$。观察可知：移除节点 $4$ 后，将得到三棵彼此同构的树（此处均为路径图），即 $\{5, 1, 7, 13\}$、$\{8, 2, 11, 6\}$ 和 $\{3, 12, 9, 10\}$，图中分别记为 $A$、$B$ 和 $C$。

• $A$ 与 $B$ 之间的同构映射 $f$：$f(5) = 8$，$f(1) = 2$，$f(7) = 11$，$f(13) = 6$。
• $A$ 与 $C$ 之间的同构映射 $f$：$f(5) = 3$，$f(1) = 12$，$f(7) = 9$，$f(13) = 10$。
• $B$ 与 $C$ 之间的同构映射 $f$：$f(8) = 3$，$f(2) = 12$，$f(11) = 9$，$f(6) = 10$。

当然，这些树之间还存在其他可能的同构映射。

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 \lt 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.

输入的第一行包含一个整数：$N$（$3 \le N \le 4000$），表示给定树中的节点数量。接下来的 $N - 1$ 行每行包含两个整数：$a_i$ $b_i$（$1 \le a_i \lt b_i \le N$），表示树中的一条边 $(a_i,b_i)$。保证给定树中任意两个节点均可通过若干条边相互连通。

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.

在一行中输出一个整数，表示通过恰好移除一个“好”的割点所能得到的互不连通的树的最大数目；若不存在这样的“好”割点，则输出 $-1$。

Explanation for the sample input/output #1

This is the example from the problem description.

样例输入/输出 #1 的说明

这是题目描述中的示例。