Chain Partitioning in a Tree

Farmer John has N ranches connected by N - 1 roads forming a tree. After many years of managing his ranches, he believes that problems on chains are simpler than on trees. Therefore, he plans to partition the tree into several chains and assign each chain to a worker. In order to avoid any dispute, he requires that every chain must have exactly K roads.

For each integer K with 1 ≤ K ≤ N - 1, determine whether it is possible to partition all the roads into disjoint chains such that each chain has exactly K roads. Output a binary string of length N - 1 where the K-th character is '1' if such a partition exists for chains of length K and '0' otherwise.

Note: A chain is defined as a simple path (i.e. a sequence of adjacent roads) and every road must belong to exactly one chain. Also, if N - 1 is not divisible by K, the partition is impossible.

inputFormat

The first line contains an integer N (the number of ranches). The following N - 1 lines each contain two integers u and v (1 ≤ u, v ≤ N) denoting a road between ranch u and ranch v.

outputFormat

Output a binary string of length N - 1. The K-th character should be '1' if it is possible to partition the tree into chains of exactly K roads, and '0' otherwise.

sample

2
1 2

1