Description

Farmer John has $N$ pastures, connected by $N-1$ roads, forming a tree.

But after 28 years of running the farm (translator's note: USACO was founded in 1992), FJ feels that dealing with tree problems is very troublesome, and he thinks problems on a single path are easier.

So he decides to split the whole tree into several chains, and give the management of each chain to a worker. To avoid possible disputes, he wants all chains to have the same length.

FJ now wants to know, for each $K$ satisfying $1 \leq K \leq N-1$, whether there exists a way to partition the entire tree into several chains such that every chain has length exactly $K$.

Input Format

The first line contains an integer $N$ ($1 \leq N \leq 10^5$).

The next $N-1$ lines each contain two integers $u, v$ ($1 \leq u, v \leq N$), describing a road connecting $u$ and $v$.

Output Format

Output a 0/1 string of length $N-1$. The $i$-th character is $1$ if and only if there exists a partition plan such that the whole tree is partitioned into several chains and every chain has length exactly $i$; otherwise, the $i$-th character is $0$.

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

Hint

Sample Explanation

When $K = 1, 2, 3$, there is a valid partition plan.

One valid partition plan for $K = 3$ is:

$13-12-11-8, 10-9-8-6, 7-6-2-3, 5-4-2-1$

Subtasks

• Test points $2 \sim 4$ satisfy that there is at most one node whose degree is greater than $2$.
• Test points $5 \sim 8$ satisfy $N \leq 10^3$.
• Test points $9 \sim 15$ have no special constraints.

Translated by ChatGPT 5