Задача D. Листовая медиана

Автор:И. Блинов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Деревом называется связный неориентированный граф без циклов. Для заданного дерева требуется выбрать такую вершину, чтобы суммарное расстояние от неё до всех листьев было максимальным.

Напишите программу, принимающую описание дерева и выводящую вершину с максимальным суммарным расстоянием до листьев. Если таких вершин несколько, выведите минимальную по номеру.

Формат входного файла

Входной файл содержит целое число N, за которым следует N − 1 описаний рёбер. Описание ребра номер i содержит два целых числа ui vi — номера вершин, которые соединены этим ребром.

Формат выходного файла

Выходной файл должен содержать единственное целое число — номер искомой вершины.

Ограничения

2 ≤ N ≤ 105, 1 ≤ ui, vi ≤ N.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
1 2
1
2
3
1 2
1 3
1
3
7
1 4
2 3
2 4
2 5
4 6
4 7
3

0.039s 0.008s 15