P4228 [清华集训 2017] 榕树之心

深秋。冷风吹散了最后一丝夏日的暑气，也吹落了榕树脚下灌木丛的叶子。相识数年的 Evan 和 Lyra 再次回到了小时候见面的茂盛榕树之下。小溪依旧，石桥依旧，榕树虽是历经荣枯更迭，依旧亭亭如盖，只是 Evan 和 Lyra 再也不是七八年前不经世事的少年了。 …… “已经快是严冬了，榕树的叶子还没落呢……” “榕树是常绿树，是看不到明显的落叶季节的……” “唉……想不到已经七年了呢。榕树还是当年的榕树，你却不是当年的你了……” “其实又有什么是一成不变的呢，榕树常绿，翠绿树冠的宏观永恒，是由无数细小树叶的荣枯更迭组成的。在时间的流逝中一切都在不断变化着呢……” “但你看这榕树，日日如此，季季如此，年年如此，仿佛亘古不变般，盘根错节，郁郁葱葱。我在想，或许成为一棵树更好吧，任时间从枝叶间流过，我只守这一片绿荫就好。” “榕树固然长久，但在这无限的时光里，终归是要湮灭于尘土的。与其像榕树一般，植根于一方泥土中感受年复一年的四季更替。倒不如在有限的时间里看过尽可能多的世界吧。再说了，榕树虽生长缓慢，却依旧会在每年春天抽出一根新的枝条去向外探索的呢……” “真的吗，榕树在她漫长的一生里，就是这样往外一步步探索的吗？” “毕竟就算树冠看起来一成不变，榕树也会随着时间周期变化，春天到了自然就是生长的时候了，她也应当做出对应的表现吧……” “相比于对季节更替做出本能的生长，我倒宁愿相信，榕树有一颗活跃的的，探索的心。” “其实榕树是有心的，榕树刚刚种下的时候，心就在根的地方发芽了。以后每年春天榕树长出新枝条的时候，心就会向着新枝条的方向移动一点，这样就能更靠近外面的世界了。你看这头顶上的枝条，纵横交错，其实心已经在这枝杈间，移动了数十载了呢……” “哇，也就是说，这密密麻麻的树杈中的某个地方，藏着这棵榕树的心吗？” “没错，可是要知道它在哪，就得另花一番功夫了……” “呀，这时候想想，一株树还是不如一个人好……比如你，要是这样贴上去的话，就能听到跳动的声音呢……” ……

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

从标准输入读入数据。 输入第一行一个两个正整数 $W,T$，分别表示子任务编号（在样例中 $W=0$）和数据组数，接下来是 $T$ 组数据的描述，对于每组数据： 第一行一个正整数 $n$ 表示树上结点的个数。 接下来 $n-1$ 行，每行两个正整数 $a_i,b_i$，表示编号 $a_i,b_i$ 的结点间有一条树边，保证 $a_i \neq b_i$ 并且输入的 $n-1$ 条边恰好构成了一棵树。

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

**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$。