Description

A banyan can be abstracted as a rooted tree with $n$ nodes, numbered $1 \sim n$, where node $1$ is the root. Initially, the tree has only node $1$, and the heart is at node $1$. After that, at each step, the tree grows a new node: specifically, a node adjacent to some currently existing node is added to the tree. Then, the heart moves one step along the simple path from the heart to the newly added node. This tree with $n$ nodes has many possible growth orders, and different orders may lead to different final positions of the heart. Now Evan and Lyra want to know: which nodes could possibly be the final resting position of the heart when the growth process ends?

For example, consider a tree of size $4$ with edges $\{<1,2>,<1,3>,<1,4>\}$. There are three different growth orders that make the heart end at nodes $2$, $3$, and $4$, respectively:

Finally ending at node $2$:

• Grow $3$ from $1$, the heart moves from $1$ to $3$,
• Grow $4$ from $1$, the heart moves from $3$ back to $1$,
• Grow $2$ from $1$, the heart moves from $1$ to $2$.

Finally ending at node $3$:

• Grow $2$ from $1$, the heart moves from $1$ to $2$,
• Grow $4$ from $1$, the heart moves from $2$ back to $1$,
• Grow $3$ from $1$, the heart moves from $1$ to $3$.

Finally ending at node $4$:

• Grow $2$ from $1$, the heart moves from $1$ to $2$,
• Grow $3$ from $1$, the heart moves from $2$ back to $1$,
• Grow $4$ from $1$, the heart moves from $1$ to $4$.

We can prove that there is no growth order that makes the heart end at node $1$.

Input Format

Read from standard input.

The first line contains two positive integers $W, T$, representing the subtask identifier (in the samples $W = 0$) and the number of test cases. Then follow $T$ test cases. For each test case:

• The first line contains a positive integer $n$, the number of nodes in the tree.
• The next $n - 1$ lines each contain two positive integers $a_i, b_i$, indicating there is a tree edge between nodes numbered $a_i$ and $b_i$. It is guaranteed that $a_i \neq b_i$ and the $n - 1$ edges form a tree.

Output Format

Output to standard output.

If the input $W$ is not equal to $3$, for each test case output a line containing a length-$n$ $01$ string. The $i$-th character indicates whether node $i$ could be the final position of the heart. A $1$ means possible, and a $0$ means impossible.

If the input $W$ equals $3$, then for each test case output a single character indicating the answer for node $1$.

0 3
4
1 2
1 3
1 4
6
1 2
1 3
1 4
4 5
5 6
10
1 2
1 3
3 4
3 5
3 6
4 7
7 8
8 9
9 10

0111
000101
0000001010

Hint

TestPoint 1 [10 pts]

• $T \leq 50; n \leq 15$.

TestPoint 2 [10 pts]

• $T \leq 20; n \leq 10^5$. For every node except node $1$, the degree (including its parent) is at most $2$.

TestPoint 3 [10 pts]

• $T \leq 200; n \leq 100$. Only output a single character indicating the answer for node $1$, i.e., it suffices to ensure the correctness for node $1$.

TestPoint 4 [35 pts]

• $T \leq 20; n \leq 10^3$.

TestPoint 5 [35 pts]

• $T \leq 20; n \leq 10^5$.

Translated by ChatGPT 5