Ферма Фермера Джона состоит из \(N\) пастбищ (\(1 \leq N \leq 10^5\)) соединённых
\(N-1\) дорогами, так, что любое пастбище достижимо из любого пастбища. То есть
ферма представляет собой дерево.
ФД планирует разделить множество дорог на несколько путей и делегировать
ответственность за каждый путь специальному человеку. Чтобы избежать раздора,
он хочет, чтобы все пути имели одинаковую длину. Он хочет узнать для каких
длин существуют такие разбиения.
Более точно для каждого \(1 \leq K \leq N-1\), помогите ФД определить,
могут ли дороги быть распределены на пути длиной ровно \(K\).
ОЦЕНИВАНИЕ:
- В тестах 2-4 дерево образовывает звезду; не более одной вершины имеет степень более двух.
- В тестах 5-8 \(N\le 10^3\).
- В тестах 9-15 нет дополнительных ограничений.
ФОРМАТ ВВОДА (файл deleg.in):
Первая строка содержит целое число
\(N\).
Каждая из следующих \(N-1\) строк содержит целые числа \(a\) и \(b\), описывающие
ребро между вершинами \(a\) и \(b\). Все \(a\) и \(b\) в интервале \(1 \ldots N\).
ФОРМАТ ВЫВОДА (файл deleg.out):
Выведите битовую строку длины \(N-1.\) Для каждого \(1\le K\le N-1,\) \(K\)-ый бит
строки слева равный 1 означает, что возможно разбиение ребер на пути длины ровно
\(K\) и равный \(0\) в противном случае.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
13
1 2
2 3
2 4
4 5
2 6
6 7
6 8
8 9
9 10
8 11
11 12
12 13
|
111000000000
|