Delegation (Gold)

Farmer John's farm consists of $N$ pastures ($2 \leq N \leq 10^5$) connected by $N-1$ roads, so that any pasture is reachable from any other pasture. That is, the farm is a tree. After 28 years of dealing with the tricky algorithmic problems that arise from trees, FJ has decided that a tree-shaped farm is too complex. He believes algorithmic problems are simpler on paths.

So he plans to partition the set of roads into several paths and delegate each path to a farm hand. To avoid contention, every path must have the same length. For which lengths does such a partition exist?

For each $1 \leq K \leq N-1$, determine whether the roads can be partitioned into paths of length exactly $K$.

The first line contains a single integer $N$. Each of the next $N-1$ lines contains two integers $a$ and $b$, describing an edge between pastures $a$ and $b$. Both $a$ and $b$ are in the range $1$ to $N$.

Output a bit string of length $N-1$. The $K$th bit from the left is 1 if the edges can be partitioned into paths of length exactly $K$, and 0 otherwise.

The tree can be partitioned into paths of length $K$ for $K=1,2,3$. For $K=3$, one possible set of paths is 13-12-11-8, 10-9-8-6, 7-6-2-3, 5-4-2-1.