题目背景

自选题 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 是否一定能在有限次行动内获胜。

输入格式

第 $1$ 行：三个整数 $n,m,q$，分别表示无向连通图的点数，边数以及游戏的次数。

接下来 $m$ 行：每行两个整数 $x,y$，描述图中的一条无向边。

接下来 $q$ 行：每行两个整数 $a,b$，表示一局游戏中双方的初始位置。

输出格式

共 $q$ 行：对于每局游戏，如果 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

提示

【样例解释】

第一组询问中，$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\%)$： 无特殊限制。