CF1998D.Determine Winning Islands in Race

MOOOOOOOOOOOOOOOOO

—— Bessie the Cow，《The Art of Racing on Islands》

农夫 John 的两头奶牛，Bessie 和 Elsie，计划在 $n$ 个岛屿上进行比赛。有 $n-1$ 条主桥，连接着每个岛屿 $i$ 和岛屿 $i+1$，其中 $1 \leq i \leq n-1$。此外，还有 $m$ 条备选桥。Elsie 可以使用主桥和备选桥，而 Bessie 只能使用主桥。所有桥都是单向的，只能从编号较小的岛屿通向编号较大的岛屿。

一开始，Elsie 在岛屿 $1$，Bessie 在岛屿 $s$。两头奶牛轮流行动，Bessie 先行动。假设奶牛当前在岛屿 $i$，在她的回合，如果存在从岛屿 $i$ 通向岛屿 $j$ 的桥，则她可以移动到岛屿 $j$。然后，岛屿 $i$ 会坍塌，所有与岛屿 $i$ 相连的桥也会坍塌。还需注意以下规则：

• 如果没有桥连接岛屿 $i$ 到其他岛屿，则岛屿 $i$ 坍塌，这头奶牛被淘汰出比赛。
• 如果另一头奶牛也在岛屿 $i$，那么在这头奶牛移动到其他岛屿后，岛屿坍塌，另一头奶牛也被淘汰出比赛。
• 岛屿或桥坍塌后，任何奶牛都不能再使用它们。
• 如果一头奶牛被淘汰，她在之后的比赛中将跳过回合。

比赛在任意一头奶牛到达岛屿 $n$ 时结束。可以证明，无论奶牛们采取何种策略，至少有一头奶牛能到达岛屿 $n$。只有当 Bessie 先到达岛屿 $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$ 的二进制字符串，表示每个起点 $s$ 的结果。如果 Bessie 能获胜，则第 $i$ 个字符为 $1$，否则为 $0$。

在第一个测试用例中，没有备选桥，Elsie 无法超越 Bessie 先到达岛屿 $n$，因此无论 Bessie 从哪个岛屿出发，她都会获胜，因为她总是先行动。

在第二个测试用例中，如果 Bessie 从岛屿 $3$ 出发，她会输，因为：

• Bessie 的回合：从岛屿 $3$ 通过主桥到达岛屿 $4$。
• Elsie 的回合：从岛屿 $1$ 通过主桥到达岛屿 $2$。
• Bessie 的回合：从岛屿 $4$ 通过主桥到达岛屿 $5$。
• Elsie 的回合：从岛屿 $2$ 通过备选桥到达岛屿 $6$。Elsie 先到达岛屿 $n$。

由 ChatGPT 4.1 翻译