#P18078. Astra

Astra

Astra

给定一棵有 nn 个顶点的树,顶点编号为 11 到 nn。最初只有顶点 ss 被标记。

Alice 先手,随后与 Bob 轮流行动。每一轮必须依次标记 pp 个此前没有被标记的顶点 a1,a2,…,apa_1,a_2,\ldots,a_p,满足:

  • 1≤p≤k1\le p\le k;
  • a1a_1 与某个已标记顶点相邻;
  • 对每个 2≤i≤p2\le i\le p,aia_i 与 ai−1a_{i-1} 相邻。

每个顶点只能标记一次。标记最后一个顶点的玩家获胜。

假设双方最优,请对每个 s=1,2,…,ns=1,2,\ldots,n,判断谁获胜。

输入格式

第一行整数 TT。每组第一行两个整数 n,kn,k,接下来 n−1n-1 行,每行两个整数 ui,viu_i,v_i,表示树的一条边。

输出格式

每组输出一行长度为 nn 的 01 字符串。第 ss 位为 1 表示以 ss 为初始标记顶点时 Alice 获胜,为 0 表示 Bob 获胜。

数据范围

  • 1≤T≤1001\le T\le100;
  • 2≤n≤20002\le n\le2000,1≤k<n1\le k<n;
  • 1≤ui,vi≤n1\le u_i,v_i\le n,输入保证构成树;
  • 所有数据的 nn 之和不超过 20002000。

样例 1

输入:

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

输出:

011000
000
101