小丑返回哥谭市执行另一个邪恶计划。在哥谭市,有 $$$N$$$ 街道交叉口(编号从 $$$1$$$ 到 $$$N$$$)和 $$$M$$$ 街道(编号从 $$$1$$$ 到 $$$M$$$)。每条街道连接两个不同的路口,并且两个路口最多由一条街道连接。
为了实现他的邪恶计划,小丑需要使用奇数条街道,这些街道一起形成一个循环。也就是说,对于路口 $$$S$$$ 和偶数正整数 $$$k$$$,存在一系列路口 $$$S、s_1、\ldots、s_k、S$$$,使得存在连接 (a) $$$S$$$ 和 $$$s_1$$$、(b) $$$s_k$$$ 和 $$$S$$$ 和 (c) 的街道$$$s_{i-1}$$$ 和 $$$s_i$$$ 对于每个 $$$i = 2, \ldots, k$$$。
然而,警察正在控制哥谭市的街道。每天 $$$i$$$,他们监控所有街道的不同子集,其中包含连续数字 $$$j$$$:$$$l_i \leq j \leq r_i$$$。当然,这些受监控的街道不能成为小丑计划的一部分。对于警察来说不幸的是,小丑在哥谭市警察局内有间谍;他们告诉他哪一天哪些街道受到监控。现在小丑想知道,在给定的天数内,他是否可以执行他的邪恶计划。在这样的一天,必然存在一个循环的街道,由奇数条当天不受监控的街道组成。
输入
输入的第一行包含三个整数 $$$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$$$,表示所有带有 $$$l_i \leq j \leq r_i$$$ 的街道 $$$j$$$ 在 $$$i$$$ ($$$1 \leq i \leq Q$$$) 当天被警察检查。
输出
您的输出将包含 $$$Q$$$ 行。如果小丑可以在 $$$i$$$ 天执行他的计划,则 $$$i$$$ ($$$1 \leq i \leq Q$$$) 行包含“YES”,否则包含“NO”。
示例
输入 #1
6 8 2 1 3 1 5 1 6 2 5 2 6 3 4 3 5 5 6 4 8 4 7
输出 #1
NO YES
注意
评分:
子任务:
1. (6 分) $$$1 \leq N, M, Q \leq 200$$$
2.(8分)$$$1 \leq N, M, Q \leq 2\,000$$$
3. (25 分) $$$l_i = 1$$$ for $$$i = 1, \ldots, Q$$$
4. (10 分) $$$l_i \leq 200$$$ for $$$i = 1, \ldots, Q$$$
5.(22 点)$$$Q \leq 2\,000$$$
6.(29分)没有进一步的限制
示例测试中的图表: