D. Тимофей и плоское дерево
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У маленького Тимофея есть большое дерево — неориентированный связный граф из n вершин, не содержащий ни одного простого цикла. Он очень любит по нему гулять. Дерево Тимофея плоское и когда он гуляет по нему, он видит всё дерево целиком. Вполне естественно, что, находясь в вершине, он видит дерево подвешенным за эту вершину.

Тимофей считает, что чем больше в дереве вершин, поддеревья которых попарно неизоморфны, тем лучше выглядит подвешенное дерево. Под поддеревом вершины подвешенного дерева он понимает подграф, состоящий из этой вершины и всех ее потомков. Помогите ему встать в такую вершину, что размер максимального подмножества вершин, поддеревья которых попарно неизоморфны при подвешивании за эту вершину, был максимально возможным.

Поддеревья вершин u и v изоморфны, если число сыновей у u и v совпадают, и можно так упорядочить сыновей, что поддерево первого сына u изоморфно поддереву первого сына v, поддерево второго сына u изоморфно поддереву второго сына v, и так далее. В частности, поддеревья, состоящие из одной вершины, всегда изоморфны друг другу.

Входные данные

В первой строке находится одно целое число n(1 ≤ n ≤ 105) — количество вершин в дереве.

В следующих n - 1 строках заданы по два числа ui и vi (1 ≤ ui, vi ≤ 105, ui ≠ vi), означающие номера вершин, соединенных i-м ребром.

Гарантируется, что заданный граф является деревом.

Выходные данные

Выведите одно число — номер вершины, в которую надо встать Тимофею. Если ответов несколько, можно вывести любой.

Примеры
Входные данные
3
1 2
2 3
Выходные данные
1
Входные данные
7
1 2
4 2
2 3
5 6
6 7
3 7
Выходные данные
1
Входные данные
10
1 7
1 8
9 4
5 1
9 2
3 5
10 6
10 9
5 10
Выходные данные
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: 


  1     9
 /\    /\
7  8  4  2