← 返回题目列表

Codeforces · 763/D

D. 蒂莫菲和一棵扁树

中文机器翻译题面 查看原题

小蒂莫菲有一棵大树——一个有 n 个顶点且没有简单循环的无向连通图。他喜欢沿着它散步。他的树是平的,所以当他沿着树行走时,他可以看到它的全部。很自然地,当他站在一个顶点上时,他将树视为一棵有根的树,根就在这个顶点上。

Timofey 假设树中非同构子树越多,树就越漂亮。顶点的子树是包含该顶点及其所有后代的子图。你应该告诉蒂莫菲他应该站在哪个顶点才能看到最美丽的有根树。

如果u的子树数量等于v的子树数量,则顶点u和v的子树是同构的,并且它们的子树可以以这样的方式排列:u的第一个儿子的子树与v的第一个儿子的子树同构,u的第二个儿子的子树与v的第二个儿子的子树同构,依此类推。特别地,由单个顶点组成的子树是彼此同构的。

输入

第一行包含单个整数 n (1 ≤ n ≤ 105) — 树中的顶点数。

接下来的 n - 1 行中的每一行都包含两个整数 ui 和 vi (1 ≤ ui, vi ≤ 105, ui ≠ vi),表示第 i 条边连接的顶点。

保证给定的图是一棵树。

输出

打印单个整数 - Timofey 应该站立的顶点的索引。如果有很多答案,您可以打印其中任何一个。

示例

输入 #1

3
1 2
2 3

输出 #1

1

输入 #2

7
1 2
4 2
2 3
5 6
6 7
3 7

输出 #2

1

输入 #3

10
1 7
1 8
9 4
5 1
9 2
3 5
10 6
10 9
5 10

输出 #3

2

注意

在第一个例子中,我们可以站在顶点 1 或顶点 3 上,这样每个子树都是非同构的。如果我们站在顶点 2 处,则顶点 1 和 3 的子树是同构的。

在第二个例子中,如果我们站在顶点1,那么只有顶点4和5的子树是同构的。

在第三个例子中,如果我们站在顶点1,那么顶点2、3、4、6、7和8的子树是同构的。如果我们站在顶点 2 上,那么只有顶点 3、4、6、7 和 8 的子树是同构的。如果我们站在顶点 5,那么顶点 2、3、4、6、7 和 8 的子树是同构的,顶点 1 和 9 的子树也是同构的: