P7353 [2020-2021 集训队作业] Tom & Jerry

自选题 by ix35

给定一张包含 $n$ 个顶点和 $m$ 条边的 **无向连通图**，Tom 和 Jerry 在图上进行了 $q$ 次追逐游戏。 在第 $i$ 次游戏中，Tom 一开始位于顶点 $a_i$，而 Jerry 一开始位于顶点 $b_i$（双方任何时候都知道自己和对方的位置），追逐规则如下： - Jerry 和 Tom 交替行动，Jerry 先行动。 - Jerry 每次行动可以通过无向图中的 **任意多条边**（可以选择不移动），但是在移动过程中不能经过 Tom 当前所在的结点，否则就会被抓住。 - Tom 每次行动只能通过无向图中的 **至多一条边**（可以选择不移动）。 - 如果 Tom 在一次行动后到达了 Jerry 的位置，那么 Tom 胜利。 Tom 尽量想要胜利，而 Jerry 会尽量阻止 Tom 胜利。 现在你需要对于每一局游戏，求出 Tom 是否一定能在有限次行动内获胜。

无

无

【样例解释】  第一组询问中，$a_1=6,\ b_1=4$，则 Jerry 先走到 $2$ 处，此后每一回合，若 Tom 行动完后与 Jerry 相邻，Jerry 只需要移动到环 $[1,2,3,4]$ 中与 Tom 不相邻的那个点，可保证 Tom 不胜。 第二组询问中，$a_2=4,\ b_2=5$，无论 Jerry 如何行动，Tom 只需走到 $6$ 处，此后 Jerry 可能在 $\{5,7,8\}$，无论如何 Tom 都可以一步追到。 第三组询问中，$a_3=5,\ b_3=7$，则 Jerry 按照第一组询问中的策略即可使得 Tom 无法获胜。 【数据范围】 **本题采用捆绑测试。** 对于 $100\%$ 的数据，$1\leq n,m,q\leq 10^5$，$1\leq x,y,a,b\leq n$，$a_i\ne b_i$。 保证给出的无向图连通，且不含重边和自环。 $\text{Subtask 1}\ (10\%)$： $n,m,q\leq 10$。 $\text{Subtask 2}\ (16\%)$： $n,m,q\leq 100$。 $\text{Subtask 3}\ (24\%)$： $n,m,q\leq 1000$。 $\text{Subtask 4}\ (16\%)$： $m=n$。 $\text{Subtask 5}\ (34\%)$： 无特殊限制。