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

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

题目背景

自选题 by ix35

题目描述

给定一张包含 nn 个顶点和 mm 条边的 无向连通图,Tom 和 Jerry 在图上进行了 qq 次追逐游戏。

在第 ii 次游戏中,Tom 一开始位于顶点 aia_i,而 Jerry 一开始位于顶点 bib_i(双方任何时候都知道自己和对方的位置),追逐规则如下:

  • Jerry 和 Tom 交替行动,Jerry 先行动。

  • Jerry 每次行动可以通过无向图中的 任意多条边(可以选择不移动),但是在移动过程中不能经过 Tom 当前所在的结点,否则就会被抓住。

  • Tom 每次行动只能通过无向图中的 至多一条边(可以选择不移动)。

  • 如果 Tom 在一次行动后到达了 Jerry 的位置,那么 Tom 胜利。

Tom 尽量想要胜利,而 Jerry 会尽量阻止 Tom 胜利。

现在你需要对于每一局游戏,求出 Tom 是否一定能在有限次行动内获胜。

输入格式

11 行:三个整数 n,m,qn,m,q,分别表示无向连通图的点数,边数以及游戏的次数。

接下来 mm 行:每行两个整数 x,yx,y,描述图中的一条无向边。

接下来 qq 行:每行两个整数 a,ba,b,表示一局游戏中双方的初始位置。

输出格式

qq 行:对于每局游戏,如果 Tom 可以在有限个回合内获胜则输出 Yes,否则输出 No

8 10 3
1 2
2 3
3 4
4 1
6 4
5 6
6 7
8 7
8 5
8 6
6 4
4 5
5 7

No
Yes
No

提示

【样例解释】

第一组询问中,a1=6, b1=4a_1=6,\ b_1=4,则 Jerry 先走到 22 处,此后每一回合,若 Tom 行动完后与 Jerry 相邻,Jerry 只需要移动到环 [1,2,3,4][1,2,3,4] 中与 Tom 不相邻的那个点,可保证 Tom 不胜。

第二组询问中,a2=4, b2=5a_2=4,\ b_2=5,无论 Jerry 如何行动,Tom 只需走到 66 处,此后 Jerry 可能在 {5,7,8}\{5,7,8\},无论如何 Tom 都可以一步追到。

第三组询问中,a3=5, b3=7a_3=5,\ b_3=7,则 Jerry 按照第一组询问中的策略即可使得 Tom 无法获胜。

【数据范围】

本题采用捆绑测试。

对于 100%100\% 的数据,1n,m,q1051\leq n,m,q\leq 10^51x,y,a,bn1\leq x,y,a,b\leq naibia_i\ne b_i

保证给出的无向图连通,且不含重边和自环。

Subtask 1 (10%)\text{Subtask 1}\ (10\%)n,m,q10n,m,q\leq 10

Subtask 2 (16%)\text{Subtask 2}\ (16\%)n,m,q100n,m,q\leq 100

Subtask 3 (24%)\text{Subtask 3}\ (24\%)n,m,q1000n,m,q\leq 1000

Subtask 4 (16%)\text{Subtask 4}\ (16\%)m=nm=n

Subtask 5 (34%)\text{Subtask 5}\ (34\%): 无特殊限制。