CF1386C.Joker

Joker returns to Gotham City to execute another evil plan. In Gotham City, there are $N$ street junctions (numbered from $1$ to $N$) and $M$ streets (numbered from $1$ to $M$). Each street connects two distinct junctions, and two junctions are connected by at most one street.

For his evil plan, Joker needs to use an odd number of streets that together form a cycle. That is, for a junction $S$ and an even positive integer $k$, there is a sequence of junctions $S, s_1, \ldots, s_k, S$ such that there are streets connecting (a) $S$ and $s_1$, (b) $s_k$ and $S$, and (c) $s_{i-1}$ and $s_i$ for each $i = 2, \ldots, k$.

However, the police are controlling the streets of Gotham City. On each day $i$, they monitor a different subset of all streets with consecutive numbers $j$: $l_i \leq j \leq r_i$. These monitored streets cannot be a part of Joker's plan, of course. Unfortunately for the police, Joker has spies within the Gotham City Police Department; they tell him which streets are monitored on which day. Now Joker wants to find out, for some given number of days, whether he can execute his evil plan. On such a day there must be a cycle of streets, consisting of an odd number of streets which are not monitored on that day.

小丑重返哥谭市，准备实施另一项邪恶计划。在哥谭市中，共有 $N$ 个路口（编号为 $1$ 至 $N$）和 $M$ 条街道（编号为 $1$ 至 $M$）。每条街道连接两个不同的路口，且任意两个路口之间至多由一条街道相连。

为实施其邪恶计划，小丑需要使用奇数条街道构成一个环路。即：对某个起点路口 $S$ 和某个正偶数 $k$，存在一串路口序列 $S, s_1, \ldots, s_k, S$，使得存在街道分别连接：(a) $S$ 与 $s_1$；(b) $s_k$ 与 $S$；(c) 对每个 $i = 2, \ldots, k$，连接 $s_{i-1}$ 与 $s_i$。

然而，哥谭市警察正在监控该市的街道。在第 $i$ 天，他们监控所有编号在区间 $[l_i, r_i]$ 内的街道（即编号连续的街道子集）。这些被监控的街道自然无法被小丑用于其计划。不幸的是，对于警方而言，小丑在哥谭市警察局内部安插了间谍；这些间谍会向他透露每天哪些街道被监控。现在，小丑希望判断：在给定的若干天中，是否存在某一天，使得当天未被监控的街道中存在一个由奇数条街道构成的环路。

The first line of the input contains three integers $N$, $M$, and $Q$ ($1 \leq N, M, Q \leq 200\,000$): the number of junctions, the number of streets, and the number of days to be investigated. The following $M$ lines describe the streets. The $j$-th of these lines ($1 \le j \le M$) contains two junction numbers $u$ and $v$ ($u \neq v$), saying that street $j$ connects these two junctions. It is guaranteed that any two junctions are connected by at most one street. The following $Q$ lines contain two integers $l_i$ and $r_i$, saying that all streets $j$ with $l_i \leq j \leq r_i$ are checked by the police on day $i$ ($1 \leq i \leq Q$).

输入的第一行包含三个整数 $N$、$M$ 和 $Q$（$1 \leq N, M, Q \leq 200\,000$）：分别表示路口数量、街道数量以及需要调查的天数。接下来的 $M$ 行描述街道信息。其中第 $j$ 行（$1 \le j \le M$）包含两个路口编号 $u$ 和 $v$（$u \neq v$），表示第 $j$ 条街道连接这两个路口。保证任意两个路口之间至多只有一条街道相连。随后的 $Q$ 行每行包含两个整数 $l_i$ 和 $r_i$，表示在第 $i$ 天（$1 \leq i \leq Q$），警方将检查所有满足 $l_i \leq j \leq r_i$ 的街道 $j$。

Your output is to contain $Q$ lines. Line $i$ ($1 \leq i \leq Q$) contains "YES" if Joker can execute his plan on day $i$, or "NO" otherwise.

你的输出应包含 $Q$ 行。第 $i$ 行（$1 \leq i \leq Q$）在小丑能在第 $i$ 天执行其计划时输出 “YES”，否则输出 “NO”。

The graph in the example test:

示例测试中的图：