Given an undirected connected graph with $n$ vertices and $m$ edges, Tom and Jerry play a chase game $q$ times.

In the $i$-th game, Tom starts at vertex $a_i$ and Jerry starts at vertex $b_i$ (both players always know their own and the other's position). The rules of the chase are as follows:

• Jerry and Tom take turns, with Jerry moving first.
• In each turn, Jerry can move along any number of edges in the undirected graph (he may also choose not to move), but he cannot pass through or land on the vertex where Tom is currently located, otherwise he is caught.
• In each turn, Tom can move along at most one edge (he may also choose not to move).
• If Tom reaches Jerry's position after his turn, Tom wins.

Tom wants to win, while Jerry wants to prevent Tom from winning.

For each game, determine whether Tom can guarantee a win in a finite number of turns.

Input

The first line contains three integers $n, m, q$, representing the number of vertices, the number of edges, and the number of games, respectively.

The next $m$ lines each contain two integers $x, y$, describing an undirected edge in the graph.

The next $q$ lines each contain two integers $a, b$, representing the initial positions of Tom and Jerry for a game.

Output

Output $q$ lines: for each game, output Yes if Tom can guarantee a win in a finite number of turns, otherwise output No.

Examples

Input 1

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

Output 1

No
Yes
No

Note 1

In the first query, $a_1=6, b_1=4$. Jerry can first move to vertex $2$. Thereafter, in each turn, if Jerry is adjacent to Tom after Tom's move, Jerry only needs to move to a vertex in the cycle $[1, 2, 3, 4]$ that is not adjacent to Tom, ensuring Tom cannot win.

In the second query, $a_2=4, b_2=5$. No matter how Jerry moves, Tom can simply move to vertex $6$. After that, Jerry might be in $\{5, 7, 8\}$, and in any case, Tom can catch Jerry in one move.

In the third query, $a_3=5, b_3=7$. Jerry can follow the same strategy as in the first query to prevent Tom from winning.

Subtasks

This problem uses bundled testing.

For $100\%$ of the data, $1\leq n, m, q\leq 10^5$, $1\leq x, y, a, b\leq n$, and $a_i\ne b_i$.

The given undirected graph is guaranteed to be connected and contains no multiple edges or self-loops.

• Subtask 1 ($10\%$): $n, m, q\leq 10$.
• Subtask 2 ($16\%$): $n, m, q\leq 100$.
• Subtask 3 ($24\%$): $n, m, q\leq 1000$.
• Subtask 4 ($16\%$): $m=n$.
• Subtask 5 ($34\%$): No additional constraints.