P7353 [2020-2021 CTT Assignment] Tom & Jerry

Optional problem by ix35. 2025/10/15: Added a set of [hack testdata](https://www.luogu.com.cn/ticket/BTVX280196), located in Subtask 0.

Given an **undirected connected graph** with $n$ vertices and $m$ edges, Tom and Jerry play $q$ chasing games on the graph. In the $i$-th game, Tom starts at vertex $a_i$, and Jerry starts at vertex $b_i$ (both sides always know their own and the opponent’s positions). The rules are: - Jerry and Tom move alternately, with Jerry moving first. - In each move, Jerry may traverse **any number of edges** in the undirected graph (he may also choose not to move), but during the movement he must not pass through the vertex where Tom is currently located, otherwise he is caught. - In each move, Tom may traverse **at most one edge** in the undirected graph (he may also choose not to move). - If Tom reaches Jerry’s position after a move, Tom wins. Tom tries his best to win, while Jerry tries his best to prevent Tom from winning. Now, for each game, determine whether Tom is guaranteed to win within a finite number of moves.

Line $1$: three integers $n, m, q$, representing the number of vertices, the number of edges, and the number of games. Next $m$ lines: each line contains two integers $x, y$, describing an undirected edge in the graph. Next $q$ lines: each line contains two integers $a, b$, representing the initial positions of the two players in one game.

Output $q$ lines. For each game, if Tom can win within a finite number of turns, output `Yes`; otherwise output `No`.

[Sample Explanation]  In the first query, $a_1 = 6,\ b_1 = 4$. Jerry first moves to $2$. After that, in each round, if Jerry is adjacent to Tom after Tom’s move, Jerry only needs to move to the vertex in the cycle $[1,2,3,4]$ that is not adjacent to Tom, which guarantees that Tom cannot win. In the second query, $a_2 = 4,\ b_2 = 5$. No matter how Jerry moves, Tom only needs to go to $6$. After that, Jerry may be in $\{5,7,8\}$. In any case, Tom can catch Jerry in one step. In the third query, $a_3 = 5,\ b_3 = 7$. Jerry can use the same strategy as in the first query to make it impossible for Tom to win. [Constraints] **This problem uses bundled testdata.** For $100\%$ of the data, $1 \le n,m,q \le 10^5$, $1 \le x,y,a,b \le n$, $a_i \ne b_i$. The given undirected graph is guaranteed to be connected, and has no multiple edges or self-loops. $\text{Subtask 1}\ (10\%)$: $n,m,q \le 10$. $\text{Subtask 2}\ (16\%)$: $n,m,q \le 100$. $\text{Subtask 3}\ (24\%)$: $n,m,q \le 1000$. $\text{Subtask 4}\ (16\%)$: $m = n$. $\text{Subtask 5}\ (34\%)$: no special restrictions. Translated by ChatGPT 5