Description

Kaikai’s factory is producing a magical part in an orderly way, and of course the production process is also magical. There are $n$ workers in the factory, numbered from $1 \sim n$. Between some pairs of workers, there are two-way conveyor belts for transporting parts. It is guaranteed that there is at most one conveyor belt between any two workers.

If worker $x$ wants to produce a part processed to stage $L\,(L \gt 1)$, then all workers that are directly connected to worker $x$ by a conveyor belt need to produce a part processed to stage $L - 1$ (but worker $x$ himself/herself does not need to produce a stage $L - 1$ part).

If worker $x$ wants to produce a part processed to stage $1$, then all workers that are directly connected to worker $x$ by a conveyor belt need to provide worker $x$ with one raw material.

Xuanxuan is worker $1$. Now $q$ work orders are given. The $i$-th work order means that the worker numbered $a_i$ wants to produce a part at stage $L_i$. For each work order, Xuanxuan wants to know whether he needs to provide raw materials for others. He knows that smart you can help him compute it.

Input Format

The first line contains three positive integers $n$, $m$, and $q$, representing the number of workers, the number of conveyor belts, and the number of work orders.

The next $m$ lines each contain two positive integers $u$ and $v$, indicating that there is a conveyor belt between worker $u$ and worker $v$. It is guaranteed that $u \neq v$.

The next $q$ lines each contain two positive integers $a$ and $L$, indicating that worker $a$ wants to produce a part at stage $L$.

Output Format

Output $q$ lines, each containing a string Yes or No. If producing according to the $i$-th work order requires Xuanxuan (worker $1$) to provide raw materials, output Yes on the $i$-th line; otherwise output No.

3 2 6
1 2
2 3
1 1
2 1
3 1
1 2
2 2
3 2

No
Yes
No
Yes
No
Yes

5 5 5
1 2
2 3
3 4
4 5
1 5
1 1
1 2
1 3
1 4
1 5

No
Yes
No
Yes
Yes

Hint

Sample 1 Explanation

If worker $1$ wants to produce a stage $1$ part, worker $2$ needs to provide raw materials.

If worker $2$ wants to produce a stage $1$ part, workers $1$ and $3$ need to provide raw materials.

If worker $3$ wants to produce a stage $1$ part, worker $2$ needs to provide raw materials.

If worker $1$ wants to produce a stage $2$ part, worker $2$ needs to produce a stage $1$ part, and workers $1$ and $3$ need to provide raw materials.

If worker $2$ wants to produce a stage $2$ part, workers $1$ and $3$ need to produce a stage $1$ part, and both of them need worker $2$ to provide raw materials.

If worker $3$ wants to produce a stage $2$ part, worker $2$ needs to produce a stage $1$ part, and workers $1$ and $3$ need to provide raw materials.

Sample 2 Explanation

If worker $1$ wants to produce a stage $1$ part, workers $2$ and $5$ need to provide raw materials.

If worker $1$ wants to produce a stage $2$ part, workers $2$ and $5$ need to produce a stage $1$ part, and workers $1,3,4$ need to provide raw materials.

If worker $1$ wants to produce a stage $3$ part, workers $2$ and $5$ need to produce a stage $2$ part, workers $1,3,4$ need to produce a stage $1$ part, and workers $2,3,4,5$ need to provide raw materials.

If worker $1$ wants to produce a stage $4$ part, workers $2$ and $5$ need to produce a stage $3$ part, workers $1,3,4$ need to produce a stage $2$ part, workers $2,3,4,5$ need to produce a stage $1$ part, and all workers need to provide raw materials.

If worker $1$ wants to produce a stage $5$ part, workers $2$ and $5$ need to produce a stage $4$ part, workers $1,3,4$ need to produce a stage $3$ part, workers $2,3,4,5$ need to produce a stage $2$ part, all workers need to produce a stage $1$ part, and all workers need to provide raw materials.

Constraints

There are $20$ test points in total.

For all test points, it is guaranteed that $1 \leq u, v, a \leq n$.

For test points $1\sim4$, $1 \leq n, m \leq 1000$, $q = 3$, $L = 1$.

For test points $5\sim8$, $1 \leq n, m \leq 1000$, $q = 3$, $1 \leq L \leq 10$.

For test points $9\sim12$, $1 \leq n, m, L \leq 1000$, $1 \leq q \leq 100$.

For test points $13\sim16$, $1 \leq n, m, L \leq 1000$, $1 \leq q \leq 10^5$.

For test points $17\sim20$, $1 \leq n, m, q \leq 10^5$, $1 \leq L \leq 10^9$.

Translated by ChatGPT 5