A2716. 游戏
编程题
省选/NOI-
知识点
题目描述
一次小G和小H在玩寻宝游戏，有 $n$ 个房间排成一列，编号为 $1,2,\cdots,n$ ，相邻的房间之间都有一道门。其中一部分门上锁（因此需要有对应的钥匙才能开门），其余的门都能直接打开。现在小G告诉了小H每把锁的钥匙在哪个房间里（**每把锁有且只有一把钥匙与之对应**），并作出 $p$ 次指示：第 $i$ 次让小H从第 $S_i$ 个房间出发到 $T_i$ 个房间里。但是小G有时会故意在指令中放入死路，而小H也不想浪费多余的体力去尝试，于是想事先调查清楚每次的指令是否会存在一条通路。
你是否能为小H作出解答呢？
你是否能为小H作出解答呢？
输入格式
第一行三个数字： $n,m,p$ ，代表有 $n$ 个房间， $m$ 道门上了锁，以及 $p$ 个询问。接下来$m$行，每行两个数字 $x,y$ 代表 $x$ 到 $x+1$ 的钥匙在房间 $y$ 。接下来 $p$ 行，其中第$i$行是两个整数 $S_i$，$T_i$，代表一次询问
输出格式
输出 $p$ 行，每行一个
YES或NO，分别代表能或不能到达。输入输出样例
输入 #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
输入 #2
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
说明/提示
$1\le n,p\le 10^6$ ， $0\le m <n$ ， $1\le x,y,S_i,T_i<n$ 保证 $x$ 不重复
$1\le n,p\le 10^6$ ， $0\le m <n$ ， $1\le x,y,S_i,T_i<n$ 保证 $x$ 不重复