Joker 回到了哥谭市，准备执行另一个邪恶计划。在哥谭市，有 $N$ 个街道交汇点（编号从 $1$ 到 $N$）和 $M$ 条街道（编号从 $1$ 到 $M$）。每条街道连接两个不同的交汇点，且任意两个交汇点之间最多只有一条街道。

为了实施他的邪恶计划，Joker 需要使用奇数条街道，这些街道共同构成一个环。也就是说，对于一个交汇点 $S$ 和一个偶数正整数 $k$，存在一个交汇点序列 $S, s_1, \dots, s_k, S$，使得存在连接以下点的街道：(a) $S$ 和 $s_1$，(b) $s_k$ 和 $S$，以及 (c) $s_{i-1}$ 和 $s_i$（对于每个 $i = 2, \dots, k$）。

然而，警方正在控制哥谭市的街道。在每一天 $i$，他们会监控所有编号在 $l_i \le j \le r_i$ 范围内的街道的一个子集。当然，这些被监控的街道不能成为 Joker 计划的一部分。不幸的是，Joker 在哥谭市警察局内有内应；他们告诉他哪一天监控哪些街道。现在 Joker 想知道，对于给定的若干天，他是否能执行他的邪恶计划。在这样的一天，必须存在一个由当天未被监控的街道组成的环，且该环包含奇数条街道。

输入格式

第一行包含三个整数 $N, M$ 和 $Q$ ($1 \le N, M, Q \le 200\,000$)：交汇点的数量、街道的数量以及需要调查的天数。接下来的 $M$ 行描述了街道。其中第 $j$ 行 ($1 \le j \le M$) 包含两个交汇点编号 $u$ 和 $v$ ($u \neq v$)，表示街道 $j$ 连接这两个交汇点。保证任意两个交汇点之间最多只有一条街道。接下来的 $Q$ 行包含两个整数 $l_i$ 和 $r_i$，表示在第 $i$ 天，所有编号满足 $l_i \le j \le r_i$ 的街道都被警方检查 ($1 \le i \le Q$)。

输出格式

输出包含 $Q$ 行。第 $i$ 行 ($1 \le i \le Q$) 如果 Joker 可以在第 $i$ 天执行他的计划，则输出 “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。

图 1：样例

子任务

1. (6 分) $1 \le N, M, Q \le 200$
2. (8 分) $1 \le N, M, Q \le 2\,000$
3. (25 分) $l_i = 1$ 对于 $i = 1, \dots, Q$
4. (10 分) $l_i \le 200$ 对于 $i = 1, \dots, Q$
5. (22 分) $Q \le 2\,000$
6. (29 分) 无其他限制