题目描述

题目译自 BalticOI 2020 Day1 C「Joker」

小丑回到了哥谭市准备实施另一个邪恶的计划。在哥谭市有 $N$ 个路口和 $M$ 条街道。每条街道连接着两个不同的路口，两个路口最多由一条街道连接。

为了实施他的邪恶计划，小丑需要使用奇数条街道，这些街道构成一个环。也就是说，对于一个路口 $S$ 和正偶数 $k$，存在一系列的路口 $S,s_1,\dots,s_k,S$，使得有道路分别连接 $S,s_1$ 和 $s_k,S$，且对于每个 $i=2,\dots,k$，有道路连接 $s_i,s_{i-1}$。

然而，警方控制着哥谭市的街道。第 $j$ 天他们监视了 $[l_j,r_j]$ 内的每一天街道。所以小丑无法使用这些街道。但对于警方来说不幸的是，小丑在警局里有些间谍，他们会告诉小丑警方每一天的监控计划。现在小丑想知道，给定的几天中每天是否能够实施计划。

输入格式

输入第一行三个整数 $N,M,Q$（$1\le N,M,Q\le 2\times 10^5$），分别表示路口的数量、街道的数量和需要研究的天数。

接下来的 $M$ 行，每行两个整数 $u,v$（$u\neq v$），其中的第 $j$ 行表示道路 $j$ 连接了 $u,v$ 这两个路口。

接下来的 $Q$ 行，每行两个整数 $l_i,r_i$，表示第 $i$ 天控制的街道的范围。

输出格式

输出共 $Q$ 行，每行一个字符串。

如果可以实施计划，则输出 YES，否则输出 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

数据范围与提示

本题共 $6$ 个子任务，各子任务的分值和限制如下：

子任务 $1$（$6$ 分）：$N,M,Q\le 200$。

子任务 $2$（$8$ 分）：$N,M,Q\le 2000$。

子任务 $3$（$25$ 分）：所有的 $l_i=1$。

子任务 $4$（$10$ 分）：所有的 $l_i\le 200$。

子任务 $5$（$22$ 分）：$Q\le 2000$。

子任务 $6$（$29$ 分）：无特殊限制。