P6684 [BalticOI 2020] Clown (Day1)

Because the amount of official testdata is too large, to avoid using too many resources, only part of the official data is selected as the testdata for this problem.

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.

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 $Q$ lines. On line $i$, if on day $i$ the Clown's plan can be carried out, output `YES`; otherwise output `NO`.

### 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