经过多次不成功的尝试,Mashtali 决定复制修改 AtCoder 问题。这是他复制的新问题:
有一棵树,有 $$$n$$$ 个顶点,并且一些非空顶点集固定在地面上。
两名玩家在树上互相比赛。他们交替执行以下操作:
- 从树中删除一条边,然后删除每个没有固定顶点的连接组件。无法移动的玩家失败(每条边都已被删除)。
您获得了树,但没有获得固定顶点集。您的任务是确定每个 $$$k$$$ 的游戏获胜者,前提是仅固定顶点 $$$1, 2, 3, \ldots, k$$$ 且双方都发挥最佳状态。
输入
输入的第一行包含一个整数 $$$n$$$ — 顶点数 ($$$1 \le n \le 3 \cdot 10^5$$$)。
以下 $$$n-1$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$u_i, v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) — 第 $$$i$$$ 条边的端点。保证这些边形成一棵树。
输出
打印长度为 $$$n$$$ 的字符串。如果第一个玩家赢得第 $$$i$$$ 个场景,则第 $$$i$$$ 个字符应为“1”,否则为“2”。
示例
输入 #1
5 1 2 2 3 2 4 4 5
输出 #1
11122
输入 #2
5 1 2 2 3 1 4 4 5
输出 #2
21122
输入 #3
6 1 2 2 4 5 1 6 3 3 2
输出 #3
111111
输入#4
7 1 2 3 7 4 6 2 3 2 4 1 5
输出#4
2212222
注意
下面您可以看到第一个示例中的树:
如果 $$$k = 1$$$ 那么第一个玩家可以切掉边缘 $$$(1, 2)$$$。
如果 $$$k = 2$$$ 或 $$$k = 3$$$,则第一个玩家可以切掉边 $$$(2, 4)$$$,之后只剩下边 $$$(1, 2)$$$ 和 $$$(2, 3)$$$。第二个玩家移动后,将留下一条边供第一个玩家切割。所以第一个玩家获胜。