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. But after 28 years of dealing with the tricky algorithmic problems that inevitably arise from trees, FJ 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 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\).


Subtask # Score Constraints
1 21 The tree forms a star; at most one vertex has degree greater than two.
2 29 \(N \leq 10^3\)
3 50 No additional constraints

Input format

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

Output a bit string of length \(N − 1\). For each \(1 \leq K \leq 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 1 Sample Output 1
1 2
2 3
2 4
4 5
2 6
6 7
6 8
8 9
9 10
8 11
11 12
12 13

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: \(13−12−11−8\), \(10−9−8−6\), \(7−6−2−3\), \(5−4−2−1\)

Submitting .cpp to 'Delegation'

You're not logged in! Click here to login

Compile Errors

Time Limit: 2 Seconds
Memory Limit: 1024MB
No. of ACs: 3
Your best score: 0
Source: USACO 2020 Feb, Gold

Subtask Score
1 21
2 29
3 50
4 0