English · Original
Chinese · Translation
Formal · Original
Little Timofey has a big tree — an undirected connected graph with _n_ vertices and no simple cycles. He likes to walk along it. His tree is flat so when he walks along it he sees it entirely. Quite naturally, when he stands on a vertex, he sees the tree as a rooted tree with the root in this vertex.
Timofey assumes that the **more** non-isomorphic subtrees are there in the tree, the more beautiful the tree is. A subtree of a vertex is a subgraph containing this vertex and all its descendants. You should tell Timofey the vertex in which he should stand to see the most beautiful rooted tree.
Subtrees of vertices _u_ and _v_ are isomorphic if the number of children of _u_ equals the number of children of _v_, and their children can be arranged in such a way that the subtree of the first son of _u_ is isomorphic to the subtree of the first son of _v_, the subtree of the second son of _u_ is isomorphic to the subtree of the second son of _v_, and so on. In particular, subtrees consisting of single vertex are isomorphic to each other.
## Input
First line contains single integer _n_ (1 ≤ _n_ ≤ 105) — number of vertices in the tree.
Each of the next _n_ - 1 lines contains two integers _u__i_ and _v__i_ (1 ≤ _u__i_, _v__i_ ≤ 105, _u__i_ ≠ _v__i_), denoting the vertices the _i_\-th edge connects.
It is guaranteed that the given graph is a tree.
## Output
Print single integer — the index of the vertex in which Timofey should stand. If there are many answers, you can print any of them.
[samples]
## Note
In the first example we can stand in the vertex 1 or in the vertex 3 so that every subtree is non-isomorphic. If we stand in the vertex 2, then subtrees of vertices 1 and 3 are isomorphic.
In the second example, if we stand in the vertex 1, then only subtrees of vertices 4 and 5 are isomorphic.
In the third example, if we stand in the vertex 1, then subtrees of vertices 2, 3, 4, 6, 7 and 8 are isomorphic. If we stand in the vertex 2, than only subtrees of vertices 3, 4, 6, 7 and 8 are isomorphic. If we stand in the vertex 5, then subtrees of vertices 2, 3, 4, 6, 7 and 8 are isomorphic, and subtrees of vertices 1 and 9 are isomorphic as well:
1 9
/_\_ /_\_
7 8 4 2
小蒂莫菲有一个大树——一个包含 #cf_span[n] 个顶点的无向连通图，且不含简单环。他喜欢在树上行走。他的树是平的，因此当他行走时能完全看到它。自然地，当他站在某个顶点上时，他会将树视为以该顶点为根的有根树。
蒂莫菲认为，树中非同构子树的数量越多，树就越美丽。一个顶点的子树是指包含该顶点及其所有后代的子图。你需要告诉蒂莫菲，他应该站在哪个顶点，才能看到最美丽的有根树。
顶点 #cf_span[u] 和 #cf_span[v] 的子树是同构的，当且仅当 #cf_span[u] 的子节点数等于 #cf_span[v] 的子节点数，并且它们的子节点可以按某种顺序排列，使得 #cf_span[u] 的第一个子节点的子树与 #cf_span[v] 的第一个子节点的子树同构，#cf_span[u] 的第二个子节点的子树与 #cf_span[v] 的第二个子节点的子树同构，依此类推。特别地，仅由单个顶点构成的子树彼此同构。
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 树中顶点的数量。
接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[ui] 和 #cf_span[vi] (#cf_span[1 ≤ ui, vi ≤ 105], #cf_span[ui ≠ vi])，表示第 #cf_span[i] 条边连接的两个顶点。
保证给定的图是一棵树。
请输出一个整数——蒂莫菲应该站立的顶点的编号。如果有多个答案，输出任意一个即可。
在第一个例子中，我们可以站在顶点 #cf_span[1] 或顶点 #cf_span[3]，使得每个子树都互不同构。如果我们站在顶点 #cf_span[2]，那么顶点 #cf_span[1] 和 #cf_span[3] 的子树是同构的。
在第二个例子中，如果我们站在顶点 #cf_span[1]，那么只有顶点 #cf_span[4] 和 #cf_span[5] 的子树是同构的。
在第三个例子中，如果我们站在顶点 #cf_span[1]，那么顶点 #cf_span[2], #cf_span[3], #cf_span[4], #cf_span[6], #cf_span[7] 和 #cf_span[8] 的子树是同构的。如果我们站在顶点 #cf_span[2]，那么只有顶点 #cf_span[3], #cf_span[4], #cf_span[6], #cf_span[7] 和 #cf_span[8] 的子树是同构的。如果我们站在顶点 #cf_span[5]，那么顶点 #cf_span[2], #cf_span[3], #cf_span[4], #cf_span[6], #cf_span[7] 和 #cf_span[8] 的子树是同构的，顶点 #cf_span[1] 和 #cf_span[9] 的子树也是同构的：
## Input
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 树中顶点的数量。接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[ui] 和 #cf_span[vi] (#cf_span[1 ≤ ui, vi ≤ 105], #cf_span[ui ≠ vi])，表示第 #cf_span[i] 条边连接的两个顶点。保证给定的图是一棵树。
## Output
输出一个整数——蒂莫菲应该站立的顶点的编号。如果有多个答案，输出任意一个即可。
[samples]
## Note
在第一个例子中，我们可以站在顶点 #cf_span[1] 或顶点 #cf_span[3]，使得每个子树都互不同构。如果我们站在顶点 #cf_span[2]，那么顶点 #cf_span[1] 和 #cf_span[3] 的子树是同构的。在第二个例子中，如果我们站在顶点 #cf_span[1]，那么只有顶点 #cf_span[4] 和 #cf_span[5] 的子树是同构的。在第三个例子中，如果我们站在顶点 #cf_span[1]，那么顶点 #cf_span[2], #cf_span[3], #cf_span[4], #cf_span[6], #cf_span[7] 和 #cf_span[8] 的子树是同构的。如果我们站在顶点 #cf_span[2]，那么只有顶点 #cf_span[3], #cf_span[4], #cf_span[6], #cf_span[7] 和 #cf_span[8] 的子树是同构的。如果我们站在顶点 #cf_span[5]，那么顶点 #cf_span[2], #cf_span[3], #cf_span[4], #cf_span[6], #cf_span[7] 和 #cf_span[8] 的子树是同构的，顶点 #cf_span[1] 和 #cf_span[9] 的子树也是同构的： 1 9 /_\_ /_\_7 8 4 2
Given a tree $ T = (V, E) $ with $ n $ vertices, for each vertex $ r \in V $, define the rooted tree $ T_r $ as $ T $ rooted at $ r $. For each vertex $ u \in V $, let $ S(u) $ denote the subtree of $ T_r $ rooted at $ u $ (i.e., the connected component containing $ u $ when removing the edge from $ u $ to its parent in $ T_r $).
Two subtrees $ S(u) $ and $ S(v) $ are isomorphic if there exists a bijection between their children such that the subtree rooted at the $ i $-th child of $ u $ is isomorphic to the subtree rooted at the $ i $-th child of $ v $, recursively, with single-vertex subtrees being isomorphic.
Let $ f(r) $ be the number of non-isomorphic subtrees in $ T_r $, i.e., the size of the set $ \{ \text{isomorphism class of } S(u) \mid u \in V \} $.
Find a vertex $ r^* \in V $ such that:
$$
r^* = \arg\max_{r \in V} f(r)
$$
If multiple such $ r^* $ exist, output any.
API Response (JSON)
{
"problem": {
"name": "D. Timofey and a flat tree",
"description": {
"content": "Little Timofey has a big tree — an undirected connected graph with _n_ vertices and no simple cycles. He likes to walk along it. His tree is flat so when he walks along it he sees it entirely. Quite n",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 4000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF763D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Little Timofey has a big tree — an undirected connected graph with _n_ vertices and no simple cycles. He likes to walk along it. His tree is flat so when he walks along it he sees it entirely. Quite n...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "小蒂莫菲有一个大树——一个包含 #cf_span[n] 个顶点的无向连通图，且不含简单环。他喜欢在树上行走。他的树是平的，因此当他行走时能完全看到它。自然地，当他站在某个顶点上时，他会将树视为以该顶点为根的有根树。\n\n蒂莫菲认为，树中非同构子树的数量越多，树就越美丽。一个顶点的子树是指包含该顶点及其所有后代的子图。你需要告诉蒂莫菲，他应该站在哪个顶点，才能看到最美丽的有根树。\n\n顶点 #cf_sp...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Given a tree $ T = (V, E) $ with $ n $ vertices, for each vertex $ r \\in V $, define the rooted tree $ T_r $ as $ T $ rooted at $ r $. For each vertex $ u \\in V $, let $ S(u) $ denote the subtree of $...",
"is_translate": false,
"language": "Formal"
}
]
}