Regular Forestation

题意翻译

给定一棵树，询问树上是否存在一个节点，使得删去这个节点后，剩下来的几棵树同构，如果有，输出这个节点最多将树分成了几棵子树，否则输出-1

题目描述

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.

输入输出样例

输入样例 #1

13
1 5
1 7
2 4
2 8
2 11
3 12
4 7
4 12
6 11
7 13
9 10
9 12

输出样例 #1

3

输入样例 #2

6
1 2
1 3
2 4
3 5
3 6

输出样例 #2

-1

说明

Explanation for the sample input/output #1 This is the example from the problem description.