← 返回题目列表

Codeforces · 1998/D

D. 确定比赛中获胜的岛屿

中文机器翻译题面 查看原题

Farmer John 的两只奶牛 Bessie 和 Elsie 计划在 $$$n$$$ 岛屿上比赛。有 $$$n - 1$$$ 主桥,将所有 $$$1 \leq i \leq n - 1$$$ 连接到 $$$i$$$ 岛和 $$$i + 1$$$ 岛。此外,还有 $$$m$$$ 替代桥梁。 Elsie 可以使用主桥和替代桥,而 Bessie 只能使用主桥。所有桥梁都是单向的,只能用于从指数较低的岛屿前往指数较高的岛屿。

最初,Elsie 从 $$$1$$$ 岛开始,Bessie 从 $$$s$$$ 岛开始。奶牛轮流轮流,贝西先轮流。假设这头牛在岛上$$$i$$$。在牛的回合中,如果有桥梁连接$$$i$$$岛和$$$j$$$岛,那么牛就可以移动到$$$j$$$岛。然后,$$$i$$$岛倒塌,所有连接$$$i$$$岛的桥梁也倒塌。另请注意以下事项:

- 如果没有桥梁将 $$$i$$$ 岛连接到另一个岛,那么 $$$i$$$ 岛就会崩溃,这头牛就会从比赛中被淘汰。
- 如果另一头牛也在岛上$$$i$$$,那么当这头牛移动到另一个岛后,该岛就会崩溃,另一头牛就会从比赛中被淘汰。
- 岛屿或桥梁倒塌后,任何奶牛都不能使用它们。
- 如果一头牛被淘汰,则在剩下的比赛中将跳过它们的回合。

一旦任意一头牛到达 $$$n$$$ 岛,比赛就结束。可以证明,无论奶牛采取何种策略,至少有一头奶牛到达岛屿 $$$n$$$。当且仅当贝西先到达 $$$n$$$ 岛时,她才获胜。

对于每个 $$$1 \leq s \leq n - 1$$$,确定如果 Bessie 在 $$$s$$$ 岛上开始比赛,她是否获胜。假设两头牛都遵循最优策略来确保各自的胜利。

输入

第一行包含 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) – 测试用例的数量。

每个测试用例的第一行包含 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq m \leq 2 \cdot 10^5$$$) – 岛屿的数量和替代桥梁的数量。

每个测试用例接下来的 $$$m$$$ 行包含 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u < v \leq n$$$) – 备用桥连接的岛屿。保证所有替代桥梁都是不同的,并且它们不与主要桥梁重合。

保证所有测试用例的 $$$n$$$ 总和和 $$$m$$$ 总和都不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,在新行上输出长度为 $$$n - 1$$$ 的二进制字符串。如果 Bessie 从 $$$i$$$ 岛上开始就有可能获胜,那么第 $$$i$$$ 个角色是 $$$1$$$。否则,它是$$$0$$$。

示例

输入 #1

5
6 0
6 1
2 6
6 1
1 5
10 4
1 3
1 6
2 7
3 8
15 3
2 8
4 9
8 15

输出 #1

11111
11011
10011
100001111
11000111000111

注意

在第一个测试用例中,Elsie 没有其他桥梁可以超越 Bessie 并首先到达 $$$n$$$ 岛,因此 Bessie 将在所有岛屿上获胜,因为她总是先移动。

在第二种情况下,如果 Bessie 从 $$$3$$$ 岛上开始,她就会失败,因为:

- 贝西的回合:从 $$$3$$$ 岛走一座主桥到 $$$4$$$ 岛。
- 埃尔西的回合:从 $$$1$$$ 岛走主桥到 $$$2$$$ 岛。
- 贝西的回合:从 $$$4$$$ 岛走一座主桥到 $$$5$$$ 岛。
- 轮到埃尔西:从 $$$2$$$ 岛走另一座桥到 $$$6$$$ 岛。艾尔西首先到达岛屿$$$n$$$。