У маленького Тимофея есть большое дерево — неориентированный связный граф из n вершин, не содержащий ни одного простого цикла. Он очень любит по нему гулять. Дерево Тимофея плоское и когда он гуляет по нему, он видит всё дерево целиком. Вполне естественно, что, находясь в вершине, он видит дерево подвешенным за эту вершину.
Тимофей считает, что чем больше в дереве вершин, поддеревья которых попарно неизоморфны, тем лучше выглядит подвешенное дерево. Под поддеревом вершины подвешенного дерева он понимает подграф, состоящий из этой вершины и всех ее потомков. Помогите ему встать в такую вершину, что размер максимального подмножества вершин, поддеревья которых попарно неизоморфны при подвешивании за эту вершину, был максимально возможным.
Поддеревья вершин u и v изоморфны, если число сыновей у u и v совпадают, и можно так упорядочить сыновей, что поддерево первого сына u изоморфно поддереву первого сына v, поддерево второго сына u изоморфно поддереву второго сына v, и так далее. В частности, поддеревья, состоящие из одной вершины, всегда изоморфны друг другу.
Выходные данные
Выведите одно число — номер вершины, в которую надо встать Тимофею. Если ответов несколько, можно вывести любой.
Примечание
В первом примере можно встать в вершину 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
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2
2 3
|
1
|
|
2
|
7
1 2
4 2
2 3
5 6
6 7
3 7
|
1
|
|
3
|
10
1 7
1 8
9 4
5 1
9 2
3 5
10 6
10 9
5 10
|
2
|