Painting Tree

Problem statement

Modulo is very good at drawing trees.

Over the years, Modulo has drawn a picture of a tree with $N$ vertices. The vertices of this tree are numbered from $1$ to $N$, and the vertices $a_i$ and $b_i$$(1 \ leq i \ leq N-1)$ are directly connected by edges. All vertices are not yet painted.

This wooden painting by Mr. Modulo impressed many people and was decided to be displayed in a famous museum.

This museum is visited by $N$ people in turn. Modulo decided to give each person a $1$ copy of the wood painting as a bonus for the visitors.

In addition, to satisfy the visitors, we decided to paint all the vertices of the tree paintings to be distributed. Visitors to the $k$ th $(1 \ leq k \ leq N)$ will only be satisfied if a picture that meets both of the following two conditions is distributed.

• Any two vertices whose shortest distance is a multiple of $k$ are painted in the same color.
• Any two vertices whose shortest distance is not a multiple of $k$ are painted in different colors.

Modulo has an infinite number of colors. Also, each copy may be painted differently.

For each visitor, determine if you can paint the vertices to satisfy them.

Constraint

• $1 \ leq N \ leq 10 ^ 5$
• $1 \ leq a_i, b_i \ leq N$
• All inputs are integers
• It is guaranteed that the graph given by the input is a tree.

---

input

Input is given from standard input in the following format.

$N$ $a_1$ $b_1$ $a_2$ $b_2$ $\ vdots$ $a_ {N-1}$ $b_ {N-1}$

• The $1$ line is given the integer $N$, which represents the number of vertices in the tree.
• From the $2$ line to the $N$ line, information on the edges of the tree is given. Of these, the $i + 1 (1 \ leq i \ leq N-1)$ line is given two integers $a_i, b_i$ indicating that the vertices $a_i$ and $b_i$ are connected by edges. Be done.

output

Output the string $S = s_1 s_2 \ ldots s_N$ consisting of 0 or 1 that satisfies the following.

• $s_k = 1$: $k$ Can be colored at the top of a given tree picture to satisfy the third visitor
• $s_k = 0$: $k$ Cannot color the vertices of a given tree picture to satisfy the third visitor

---

Input example 1

7 13 twenty three 3 4 4 5 4 6 6 7

Output example 1

1100111

The tree of input example 1 is as shown in the figure below.

sample_picture_1_0

For example, when $k = 2$, the condition is satisfied by painting as follows.

sample_picture_1_2

Also, when $k = 5$, the condition is satisfied by painting as follows.

sample_picture_1_1

---

Input example 2

6 1 2 twenty three 3 4 4 5 5 6

Output example 2

111111

---

Input example 3

1

Output example 3

1

Example

Input

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

Output

1100111

inputFormat

inputs are integers

• It is guaranteed that the graph given by the input is a tree.

---

input

Input is given from standard input in the following format.

$N$ $a_1$ $b_1$ $a_2$ $b_2$ $\ vdots$ $a_ {N-1}$ $b_ {N-1}$

• The $1$ line is given the integer $N$, which represents the number of vertices in the tree.
• From the $2$ line to the $N$ line, information on the edges of the tree is given. Of these, the $i + 1 (1 \ leq i \ leq N-1)$ line is given two integers $a_i, b_i$ indicating that the vertices $a_i$ and $b_i$ are connected by edges. Be done.

outputFormat

output

Output the string $S = s_1 s_2 \ ldots s_N$ consisting of 0 or 1 that satisfies the following.

• $s_k = 1$: $k$ Can be colored at the top of a given tree picture to satisfy the third visitor
• $s_k = 0$: $k$ Cannot color the vertices of a given tree picture to satisfy the third visitor

---

Input example 1

7 13 twenty three 3 4 4 5 4 6 6 7

Output example 1

1100111

The tree of input example 1 is as shown in the figure below.

sample_picture_1_0

For example, when $k = 2$, the condition is satisfied by painting as follows.

sample_picture_1_2

Also, when $k = 5$, the condition is satisfied by painting as follows.

sample_picture_1_1

---

Input example 2

6 1 2 twenty three 3 4 4 5 5 6

Output example 2

111111

---

Input example 3

1

Output example 3

1

Example

Input

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

Output

1100111

样例

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

1100111