#P18078. Astra
Astra
Astra
给定一棵有 个顶点的树,顶点编号为 到 。最初只有顶点 被标记。
Alice 先手,随后与 Bob 轮流行动。每一轮必须依次标记 个此前没有被标记的顶点 ,满足:
- ;
- 与某个已标记顶点相邻;
- 对每个 , 与 相邻。
每个顶点只能标记一次。标记最后一个顶点的玩家获胜。
假设双方最优,请对每个 ,判断谁获胜。
输入格式
第一行整数 。每组第一行两个整数 ,接下来 行,每行两个整数 ,表示树的一条边。
输出格式
每组输出一行长度为 的 01 字符串。第 位为 1 表示以 为初始标记顶点时 Alice 获胜,为 0 表示 Bob 获胜。
数据范围
- ;
- ,;
- ,输入保证构成树;
- 所有数据的 之和不超过 。
样例 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