Делегація (Золото)#10125
Ферма фермера Джона складається з пасовищ, з'єднаних n-1 дорогами так, що з будь-якого пасовища можна потрапити на будь-яке інше. Тобто, ферма є деревом. Однак після 28 років роботи з непростими алгоритмічними задачами, що виникають через дерева, фермер Джон вирішив, що ферма у формі дерева надто складна. Він вважає, що задачі простіше розв'язувати на шляхах.
Тепер його план — розбити всі дороги на кілька шляхів та доручити кожен шлях окремому працівнику. Щоб уникнути суперечок, він хоче, щоб усі шляхи були однакової довжини. Джон задається питанням: для яких довжин таке розбиття можливе?
Точніше: для кожного (1 \leq k \leq n-1) визначте, чи можна розбити всі дороги на шляхи довжини рівно .
Перший рядок містить одне ціле число (2 \leq n \leq 10^5).Кожен із наступних n-1 рядків містить по два цілих числа і , які визначають ребро між вершинами і . і набувають значень від до включно.
Виведіть бітовий рядок довжини n-1. Для кожного (1 \leq k \leq n-1), -ий символ у цьому рядку ліворуч має дорівнювати , якщо можна розбити ребра дерева на шляхи довжиною рівно , і інакше.
Дерево, наведене в прикладі, можна розділити на шляхи довжини для k = 1, 2, 3. Для k = 3 можливий набір шляхів:
13–12–11–8, 10–9–8–6, 7–6–2–3, 5–4–2–1Приклад 1