L: 木の彩色

問題文

モデューロさんは木の絵を描くのがとてもうまいです。

モデューロさんは長い年月をかけて頂点が $N$ 個である木の絵を書きました。 この木の頂点には $1$ から $N$ までの番号がついており、頂点 $a_i$ と $b_i$ $(1 \leq i \leq N-1)$ は直接辺でつながれています。 すべての頂点には色がまだ塗られていません。

モデューロさんが書いたこの木の絵はたくさんの人を感動させ、有名な美術館に飾られることが決まりました。

この美術館には順に $N$ 人の人が来場します。モデューロさんは来場者特典として、それぞれの人に $1$ 枚ずつ木の絵のコピーを配布することにしました。

さらに、来場者に満足してもらうため、配布する木の絵の頂点すべてに色を塗ることにしました。 $k$ 番目 $(1 \leq k \leq N)$ に来場する人は、以下の 2 条件を共に満たす絵が配布されたときにのみ満足します。

  • 最短距離が $k$ の倍数である任意の 2 頂点は、同じ色で塗られている。
  • 最短距離が $k$ の倍数でない任意の 2 頂点は、異なる色で塗られている。

モデューロさんが持っている色の数は無限にあります。また、それぞれのコピーで色の塗り方が違っても構いません。

それぞれの来場者に対し、その来場者を満足させるように頂点を塗ることができるかどうか判定してください。

制約

  • $1 \leq N \leq 10^5$
  • $1 \leq a_i, b_i \leq N$
  • 入力はすべて整数である
  • 入力によって与えられるグラフが木であることは保証される。

入力

入力は以下の形式で標準入力から与えられる。

$N$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{N-1}$ $b_{N-1}$
  • $1$ 行目には、木の頂点数を表す整数 $N$ が与えられる。
  • $2$ 行目から $N$ 行目には、木の辺の情報が与えられる。このうち $i+1(1 \leq i \leq N-1)$ 行目には、頂点 $a_i$ と $b_i$ が辺でつながっていることを示す 2 つの整数 $a_i,b_i$ が与えられる。

出力

以下を満たす 0 または 1 からなる文字列 $S = s_1 s_2 \ldots s_N$ を出力せよ。

  • $s_k = 1$ : $k$ 番目の来場者が満足できるよう与えられた木の絵の頂点に彩色できる
  • $s_k = 0$ : $k$ 番目の来場者が満足できるよう与えられた木の絵の頂点に彩色できない

入力例 1

7
1 3
2 3
3 4
4 5
4 6
6 7

出力例 1

1100111

入力例1の木は以下の図のようになります。

sample_picture_1_0

例えば、$k=2$ の時、以下のように塗れば条件を満たします。

sample_picture_1_2

また、$k=5$ の時、以下のように塗れば条件を満たします。

sample_picture_1_1

入力例 2

6
1 2
2 3
3 4
4 5
5 6

出力例 2

111111

入力例 3

1

出力例 3

1