Делегация (Золото)
Ферма фермера Джона состоит из n пастбищ, соединенных n - 1 дорогами так, что с любого пастбища всегда можно дойти до любого другого. То есть ферма - это дерево. Но после 28 лет работы с хитрыми алгоритмическими проблемами, которые неизбежно возникают из-за деревьев, ФД решил, что ферма в форме дерева слишком сложна. Он считает, что алгоритмические проблемы проще на путях.
Его план состоит в том, чтобы разделить множество дорог на несколько путей и передать ответственность за каждый путь достойному хозяину фермы. Для избежания разногласий он хочет, чтобы все пути были одинаковой длины. ФД задается вопросом, для каких длин существует такое разбиение.
Для каждого значения k (1 ≤ k ≤ n − 1) помогите фермеру Джону определить, можно ли разделить дороги на участки в точности длины k.
Входные данные
Первая строка содержит одно целое число n (2 ≤ n ≤ 10^5). Каждая из следующих n - 1 строк содержит два целых числа a и b, описывающих ребро между вершинами a и b. Каждое из значений a и b находится в диапазоне 1 ... n.
Выходные данные
Выведите битовую строку длины n - 1. Для каждого значения k (1 ≤ k ≤ n − 1) k - ый бит этой строки слева должен равняться 1, если можно разделить ребра дерева на пути длиной ровно k, и 0 в противном случае.
Пример
Дерево, приведенное в примере, можно разбить на пути длины k для k = 1, 2, 3. Для k = 3 возможный набор путей выглядит следующим образом:
13−12−11−8,10−9−8−6,7−6−2−3,5−4−2−1