Корова в опасности (Платина)
Загнанная в угол, Бесси ушла в дальнюю ферму. Ферма состоит из n сараев и n - 1 двунаправленных туннелей так, что между каждой парой сараев имеется уникальный путь. Каждый сарай, в котором есть только один туннель, является выходом. Когда наступит утро, Бесси появится в каком-то сарае и попытается добраться до выхода.
Но как только Бесси появится на поверхности, представители закона смогут определить ее местонахождение. Затем некоторые фермеры будут пытаться поймать Бесси у различных выходных сараев. Фермеры движутся с той же скоростью, что и Бесси (поэтому на каждом шаге каждый фермер может перемещаться из одного сарая в соседний сарай). Фермеры всегда знают, где находится Бесси, а Бесси всегда знает, где находятся фермеры. Фермеры словят Бесси, если в некоторый момент фермер оказывается в том же сарае, что и Бесси, или пересекает тот же туннель, что и Бесси. И наоборот, Бесси сбегает, если достигает выходного сарая до того, как ее поймают фермеры.
Бесси не уверена, в каком сарае ей следует выйти. Для каждого из n сараев помогите Бесси определить минимальное количество фермеров, которое потребуется чтобы поймать Бесси, если она там выйдет, предполагая, что фермеры оптимально распределятся между выходными сараями.
Входные данные
Первая строка содержит n (2 ≤ n ≤ 7 * 10^4). Каждая из следующих n − 1 строк содержит два целых числа, каждое в диапазоне 1 .. n, описывающих туннель между двумя амбарами.
Выходные данные
Выведите n строк, где i-ая строка содержит минимальное количество фермеров, необходимое для поимки Бесси, если она появится в i-ом сарае.