Задача H. Интернет по ЛЭП

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

Условие

Один из интернет-провайдеров решил опробовать новую технологию — передачу данных по линиям электропередач. Для этого на подстанциях были установлены N ретрансляторов.

Рассмотрим i-й ретранслятор и провод от него к другому ретранслятору. Количество ретрансляторов, сигнал от которых к i-му проходит через рассматриваемый провод, назовем нагрузкой на данный провод для i-го ретранслятора. Максимум из нагрузок на все провода для i-го ретранслятора называется нагрузкой на данный ретранслятор. Известно, что по проводам электросети сигнал может пройти от одного ретранслятора к другому единственным образом.

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

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

Во входном файле содержится число N — количество ретрансляторов, за которыми следуют N − 1 пар чисел ui vi, означающих, что i-ый провод соединяет ретрансляторы ui и vi.

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

В выходном файле должно содержаться N чисел a1 a2… aN, где ai — нагрузка на i-ый ретранслятор.

Ограничения

1 ≤ N ≤ 100000.

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

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

0.065s 0.010s 13