Delegation (Gold)#10125

Delegation (Gold)

1 second

128 megabytes

Very hard

Farmer John's farm consists of $n$ pastures connected by $n - 1$ n-1 roads, so that any pasture is reachable from any other pasture. That is, the farm is a tree. But after 28 years of dealing with the tricky algorithmic problems that inevitably arise from trees, Farmer John has decided that a farm in the shape of a tree is just too complex. He believes that algorithmic problems are simpler on paths.

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

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

Input

The first line contains a single integer $n$ ( $2 \leq n \leq 1 0^{5}$ 2 \leq n \leq 10^5).Each of the next $n - 1$ n - 1 lines contains two integers $a$ and $b$ , describing an edge between vertices $a$ and $b$ . Each of $a$ and $b$ is in the range $1, 2, \dots, n$ 1, 2, \ldots, n.

Output

Output a bit string of length $n - 1$ n-1. For each $k$ ( $1 \leq k \leq n - 1$ 1 \leq k \leq n-1), the $k$ -th bit of this string from the left should be $1$ if it is possible to partition the edges of the tree into paths of length exactly $k$ , and $0$ otherwise.

Examples

It is possible to partition the tree in the example into paths of length $k$ for $k = 1, 2, 3$ k = 1, 2, 3. For $k = 3$ k = 3, a possible set of paths is:

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

Example 1