#P18047. Catch the Monster
Catch the Monster
Catch the Monster
给定一个有 个顶点、 条边的森林,顶点编号为 。森林是无环的无向图,可以不连通。
怪物最初藏在其中某个未知顶点。你可以反复执行下列操作:
- 选择一个顶点 。
- 若怪物当前就在 ,则立即抓住它。
- 否则,这次操作未能抓住怪物。随后怪物可以停留在原地,也可以沿一条边移动到相邻顶点,但不能移动到本次选择的顶点 。
若存在一个预先确定的有限顶点序列,使得按此序列进行操作,无论怪物最初在哪里、每次如何移动,都能保证抓住怪物,则称这个森林是可捕获的。
共有 个询问,每次给出 。只保留编号在此区间内的顶点以及两端都保留下来的边,形成诱导子森林。判断该子森林是否可捕获。询问相互独立,怪物也只能在该次询问的子森林中活动。
输入格式
第一行三个整数 。
接下来 行,每行两个不同的顶点 ,表示一条无向边。保证输入图是森林。
接下来 行,每行两个整数 。
输出格式
每个询问输出一行:若可捕获,输出 Yes;否则输出 No。
本 Hydro 版本采用默认文本比较,请按上述大小写输出 Yes 或 No。
数据范围
,,,,,。
样例 1
输入:
10 9 3
1 2
1 3
1 8
2 5
2 6
2 7
3 4
8 9
8 10
1 3
2 6
1 10
输出:
Yes
Yes
No
样例 2
输入:
100000 1 1
1 2
1 9999
输出:
Yes