Joker

小丑回到了哥谭市，准备执行一个邪恶的计划。哥谭市有 $N$ 个路口（编号从 $1$ 到 $N$），$M$ 条道路（编号从 $1$ 到 $M$）。一条道路连接两个不同的路口，且两个路口间最多只有一条道路相连。 为了实现他的邪恶计划，小丑需要在城市中走完一个奇环。形式化地说，一个奇环为一个形如 $S,s_1,s_2,\ldots,s_k,S$ 的序列（要求 $k$ 为偶数），其中 $S$ 和 $s_1$，$s_k$ 和 $S$，以及 $\forall 1 \lt i \leq k$，$s_{i-1}$ 和 $s_i$ 之间都有道路直接相连。 然而，警察控制了城市中的部分街道。在第 $i$ 天，警察控制了编号在 $[l_i,r_i]$ 范围内的所有街道，小丑不能经过这些街道。然而小丑通过买通警察局的内鬼，了解到了警察在未来 $Q$ 天控制街道的计划，现在小丑想要知道，在哪些日子里，他的邪恶计划可以实现。

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.

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 $ ).

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. Scoring Subtasks: 1. (6 points) $ 1 \leq N, M, Q \leq 200 $ 2. (8 points) $ 1 \leq N, M, Q \leq 2\,000 $ 3. (25 points) $ l_i = 1 $ for $ i = 1, \ldots, Q $ 4. (10 points) $ l_i \leq 200 $ for $ i = 1, \ldots, Q $ 5. (22 points) $ Q \leq 2\,000 $ 6. (29 points) No further constraints

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

The graph in the example test: