A21805.游戏
省选/NOI-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
一次小G和小H在玩寻宝游戏,有 n 个房间排成一列,编号为 1,2,⋯,n ,相邻的房间之间都有一道门。其中一部分门上锁(因此需要有对应的钥匙才能开门),其余的门都能直接打开。现在小G告诉了小H每把锁的钥匙在哪个房间里(每把锁有且只有一把钥匙与之对应),并作出 p 次指示:第 i 次让小H从第 Si 个房间出发到 Ti 个房间里。但是小G有时会故意在指令中放入死路,而小H也不想浪费多余的体力去尝试,于是想事先调查清楚每次的指令是否会存在一条通路。
你是否能为小H作出解答呢?
输入格式
第一行三个数字: n,m,p ,代表有 n 个房间, m 道门上了锁,以及 p 个询问。接下来m行,每行两个数字 x,y 代表 x 到 x+1 的钥匙在房间 y 。接下来 p 行,其中第i行是两个整数 Si,Ti,代表一次询问
输出格式
输出 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≤n,p≤106 , 0≤m<n , 1≤x,y,Si,Ti<n 保证 x 不重复