Description

一棵榕树可以抽象成一棵$n$个结点的有根树，其中结点编号为$1 \sim n$，而$1$号点就是根节点。初始时，树只有一号点，而心也在一号点。之后每一步，树都会长出一个新结点，即某个和当前已经存在的某个结点相邻的结点被加入了树中，之后，心会沿着心到新加结点的简单路径移动一步。这棵$n$个结点的树有很多种生长的顺序，不同的顺序可能会导致最终心的位置不同。现在，Evan和Lyra想知道，哪些结点可能是心在生长过程结束时停留的位置呢？

例如一棵大小为$4$的树，连边为$\{<1,2>,<1,3>,<1,4>\}$，我们有三种不同的生长顺序可以让心分别停留在$2,3,4$号节点上：

最终停留在$2$号点：

从1生长出3，心从1移动到3,
从1生长出4，心从3移动回1,
从1生长出2，心从1移动到2.

最终停留在$3$号点：

从1生长出2，心从1移动到2,
从1生长出4，心从2移动回1,
从1生长出3，心从1移动到3.

最终停留在$4$号点：

从1生长出2，心从1移动到2,
从1生长出3，心从2移动回1,
从1生长出4，心从1移动到4.

而我们可以证明，不存在任何一种可能的生长顺序使得心停留在$1$号点。

Input Format

从标准输入读入数据。

输入第一行一个两个正整数$W,T$，分别表示子任务编号（在样例中$W=0$）和数据组数，接下来是$T$组数据的描述，对于每组数据：

第一行一个正整数$n$表示树上结点的个数。

接下来$n-1$行，每行两个正整数$a_i,b_i$​​，表示编号$a_i,b_i$​​的结点间有一条树边，保证$a_i \neq b_i$并且输入的$n-1$条边恰好构成了一棵树。

Output Format

输出到标准输出。

若输入的$W$不等于$3$，对于每组数据输出一行一个长度为$n$的$01$字符串，表示编号为$1 \sim n$的结点是否有可能是心最后所在的位置，若$01$字符串对应位是$1$则表示可能，为$0$则表示不可能。

若输入的$W$等于$3$，则对每组数据输出一个字符表示$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[10pts]

$T \leq 50; n \leq 15$。

TestPoint 2[10pts]

$T \leq 20; n \leq 10^5$。除了$1$号点之外，每个点度数（包括父亲）不超过$2$。

TestPoint 3[10pts]

$T \leq 200; n \leq 100$。只输出一个字符表示$1$号点答案，即保证$1$号点答案正确即可。

TestPoint 4[35pts]

$T \leq 20; n \leq 10^3$。

TestPoint 5[35pts]

$T \leq 20; n \leq 10^5$。