小蒂莫菲有一棵大树——一个有 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 的子树也是同构的: