Делегація (Золото)
Ферма фермера Джона складається з 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