#2508. 「AHOI / HNOI2018」游戏

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

一次小 G 和小 H 在玩寻宝游戏,有 nnn 个房间排成一列,编号为 1,2,,n,相邻房间之间都有 111 道门。其中一部分门上有锁(因此需要对应的钥匙才能开门),其余的门都能直接打开。

现在小 G 告诉了小 H 每把锁的钥匙在哪个房间里(每把锁有且只有一把钥匙),并作出 ppp 次指示:第 iii 次让小 H 从第 SiS_iSi 个房间出发,去第 TiT_iTi 个房间寻宝。但是小 G 有时会故意在指令里放入死路,而小 H 也不想浪费多余的体力去尝试,于是想事先调查清楚每次的指令是否存在一条通路。

你是否能为小 H 作出解答呢?

输入格式

第一行三个整数nnnmmmppp,代表共有 nnn 个房间,mmm 道门上了锁,以及 ppp 个询问。

接下来 mmm 行每行有两个整数xxxyyy,代表第 xxx 到第 x+1x + 1x+1 个房间的门上有把锁,并且这把锁的钥匙被放在了第 yyy 个房间里。输入保证 xxx 不重复。

接下来 ppp 行,其中第 iii 行是两个整数 SiS_iSiTiT_iTi,代表一次询问。

输出格式

输出 mmm 行,每行一个大写的 YESNO 分别代表能或不能到达。

样例

样例输入 1

5 4 5
1 3
2 2
3 1
4 4
2 5
3 5
4 5
2 1
3 1

样例输出 1

YES
NO
YES
YES
NO

样例解释 1

第一个询问 S=2S = 2S=2T=5T = 5T=5 的一条可行路线是:2→3→2→1→2→3→4→52 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 523212345

样例输入 2

此组样例满足特性:y≤xy \le xyx 恒成立

7 5 4
2 2
3 3
4 2
5 3
6 6
2 1
3 4
3 7
4 5

样例输出 2

YES
YES
NO
NO

样例解释 2

第一个询问 222111 房间之间没有锁所以为一条通路。

数据范围与提示

测试点编号 n m 其他特性
1 ≤1000 \le 1000 1000 ≤1000 \le 1000 1000
2 ≤1000 \le 1000 1000 ≤1000 \le 1000 1000
3 ≤105 \le 10^5 105 ≤105 \le 10^5 105 y≤xy \le xyx 恒成立
4 ≤105 \le 10^5 105 ≤105 \le 10^5 105 y≤xy \le xyx 恒成立
5 ≤105 \le 10^5 105 ≤105 \le 10^5 105
6 ≤105 \le 10^5 105 ≤105 \le 10^5 105
7 ≤106 \le 10^6 106 ≤106 \le 10^6 106 y≤xy \le xyx 恒成立
8 ≤106 \le 10^6 106 ≤106 \le 10^6 106 y≤xy \le xyx 恒成立
9 ≤106 \le 10^6 106 ≤106 \le 10^6 106
10 ≤106 \le 10^6 106 ≤106 \le 10^6 106

对于所有数据,保证 1≤n,p≤1061 \le n,p \le 10^61n,p1060≤m<n0 \le m < n0m<n1≤x,y,Si,Ti<n1 \le x, y, S_i,T_i < n1x,y,Si,Ti<n,保证 xxx 不重复。

由于本题输入文件较大,建议在程序中使用读入优化。