该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

样例下载

题目描述

小明正在纸上画一棵树。

首先，他画了一个结点，作为树的根节点。此时，树上只有一个根节点。而有一只蚂蚁此时正好在根节点处。

接下来，他会画一个新的结点，并从新结点向树上结点连一条边。这样，新结点被添加到树上。

每添加一个新结点，蚂蚁就会沿着当前所在位置到新节点的最短路径朝新节点方向爬行，但仅爬行一条边后即停止。

画完后，小明忘记了这棵树是怎么画的。

问：当小明画完这棵树后，蚂蚁可能停留在哪个节点上？

共有 5 个子任务，每个子任务包含多组数据。所有数据中，树的根结点均为 1 号结点，其他结点的编号与结点被添加到树上的顺序无关。

输入格式

第一行：两个正整数 S, T, 其中 S 表示子任务编号（在样例输入中 S=0 ），T 表示数据组数。

对于每组数据：

• 第一行：一个正整数 N;

• 接下来 N-1 行：每行两个整数 x, y, 表示点 x 和 点 y 之间有一条边。（1 ≤ x, y ≤ N）

输出格式

对于第 3 个子任务，即 S = 3，每组数据的答案占一行，每行仅包含一个字符 0 或 1，表示根节点即 1 号点有没有可能是蚂蚁最终的停留点，若有可能则输出 1，若不可能则输出 0。

对于其他子任务，每组数据的答案占一行，包含一个长度为 N 的 01 字符串，若点 i 是蚂蚁最终可能的停留点，则左数第 i 个字符输出为 1，若不可能则输出为 0。

样例输入

0 2
3
1 2
2 3
5
1 2
2 3
1 4
1 5

样例输出

001
10100

数据范围

• Subtask 1[10pts]: $S = 1; T ≤ 50; N ≤ 15$。

• Subtask 2[10pts]: $S = 2; T ≤ 20; N ≤ 10^5$。 除了根节点，其他每个点最多连着两条边。

• Subtask 3[10pts]: $S = 3; T ≤ 200; N ≤ 100$。 每组数据的答案只输出一个字符。

• Subtask 4[35pts]: $S = 4; T ≤ 20; N ≤ 10^3$。

• Subtask 5[35pts]: $S = 5; T ≤ 20; N ≤ 10^5$。