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