Description

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.

Input Format

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 Format

Output $q$ lines. For each game, if Tom can win within a finite number of turns, output Yes; otherwise output 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

Hint

[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