Description

The Clown has returned to Gotham City and is ready to carry out an evil plan. Gotham City has $N$ intersections (numbered from $1$ to $N$) and $M$ roads (numbered from $1$ to $M$). Each road connects two different intersections, and there is at most one road between any pair of intersections.

To carry out his evil plan, the Clown needs to walk through an odd cycle in the city. Formally, an odd cycle is a sequence of the form $S, s_1, s_2, \ldots, s_k, S$ (where $k$ is even), such that there is a road directly connecting $S$ and $s_1$, $s_k$ and $S$, and for all $1 \lt i \leq k$, there is a road directly connecting $s_{i-1}$ and $s_i$.

However, the police control some streets in the city. On day $i$, the police control all streets with indices in the range $[l_i, r_i]$, and the Clown cannot use these streets. By bribing an insider in the police department, the Clown has learned the police plan for controlling streets over the next $Q$ days. Now he wants to know on which days his evil plan can be carried out.

Input Format

The first line contains three integers $N, M, Q$.

The next $M$ lines each contain two integers $u, v$ (guaranteed $u \neq v$), describing street number $i$. It connects intersections $u$ and $v$. It is guaranteed that there is at most one street between any pair of intersections.

The next $Q$ lines each contain two integers $l_i, r_i$, meaning that on day $i$ the police will control all streets with indices in the range $[l_i, r_i]$.

Output Format

Output $Q$ lines.

On line $i$, if on day $i$ the Clown's plan can be carried out, output YES; otherwise output NO.

6 8 2
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
4 8
4 7

NO
YES

Hint

Sample Explanation

Subtasks

All testdata satisfy: $1 \leq N, M, Q \leq 2 \times 10^5$.

• Subtask 1 (6 points): $1 \leq N, M, Q \leq 200$.
• Subtask 2 (8 points): $1 \leq N, M, Q \leq 2 \times 10^3$.
• Subtask 3 (25 points): $\forall i \in [1, Q]$, $l_i = 1$.
• Subtask 4 (10 points): $\forall i \in [1, Q]$, $l_i \leq 200$.
• Subtask 5 (22 points): $Q \leq 2 \times 10^3$.
• Subtask 6 (29 points): No special constraints.

Translated by ChatGPT 5