## USACO 2020 February Contest, Gold

## Problem 3. Delegation

Contest has ended.

**Log in to allow submissions in analysis mode**

Thus, his plan is to partition the set of roads into several paths, and delegate responsibility for each path to a worthy farm hand. To avoid contention, he wants each path to be the same length. He wonders for which lengths there exists such a partition.

More precisely, for each $1 \leq K \leq N-1$, help Farmer John determine whether the roads can be partitioned into paths of length exactly $K$.

#### SCORING:

- In test cases 2-4 the tree forms a star; at most one vertex has degree greater than two.
- Test cases 5-8 satisfy $N\le 10^3$.
- Test cases 9-15 satisfy no additional constraints..

#### INPUT FORMAT (file deleg.in):

The first line contains a single integer $N$.The next $N-1$ lines each contain two space-separated integers $a$ and $b$ describing an edge between vertices $a$ and $b$. Each of $a$ and $b$ is in the range $1 \ldots N$.

#### OUTPUT FORMAT (file deleg.out):

Output a bit string of length $N-1.$ For each $1\le K\le N-1,$ the $K$th bit of this string from the left should equal one if it is possible to partition the edges of the tree into paths of length exactly $K$ and $0$ otherwise.#### SAMPLE INPUT:

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

#### SAMPLE OUTPUT:

111000000000

It is possible to partition this tree into paths of length $K$ for $K=1,2,3.$ For $K=3$, a possible set of paths is as follows:

Problem credits: Mark Gordon and Dhruv Rohatgi