Беси попала на дальнюю ферму.
Эта ферма состоит из \(N\) амбаров (\(2 \leq N \leq 7 \cdot 10^4\)) и \(N-1\) двунаправленных
туннелей между амбарами, так что между любыми двумя амбарами имеется путь, и он
единственный. Каждый амбар, который имеет только один туннель, является выходом.
Когда придёт утро, Беси приземлится на некоторый амбар и попытается достичь выхода.
Но в тот момент, когда Беси приземляется, закон сможет определить ее местоположение.
Некоторые фермеры начнут в различных выходных амбарах и попытаются поймать Беси.
Фермеры двигаются на той же скорости, что и Беси (поэтому в каждый момент времени
каждый фермер может перейти из своего амбара в соседний). Фермеры всё время знают,
где находится Беси, и Беси всё время знает, где находятся фермеры. Фермеры поймают
Беси, если в некоторый момент времени, один из фермеров находится в том же амбаре,
что и Беси или проходит по тому же туннелю, что и Беси. Беси сбежит, если
достигнет амбара с выходом, прежде чем любой из фермеров поймает её.
Беси не уверена в своих шансах на успех, которые зависят от количества
фермеров, которые будут за ней охотиться. Для каждого из \(N\) амбаров, в
которых может приземлиться Беси, определите минимальное количество фермеров, которое
необходимо, чтобы поймать Беси, в предположении, что фермеры распределяться
оптимально среди выходных амбаров.
ФОРМАТ ВЫВОДА (файл atlarge.in):
Первая строка ввода содержит \(N\). Каждая из последующих \(N-1\) строк
содержит два целых числа в интервале \(1 \ldots N\), описывающих туннель
между двумя амбарами.
Заметим время на тест в этой задаче больше чем по умолчанию:
4 секунды для C/C++/Pascal, и 8 секунд для Java/Python.
ФОРМАТ ВЫВОДА (файл atlarge.out):
Выведите \(N\) строк, где \(i\)-ая строка содержит минимальное количество фермеров,
необходимых, чтобы поймать Беси, если она приземлится в амбаре \(i\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
1 2
1 3
3 4
3 5
4 6
5 7
|
3
1
3
3
3
1
1
|