#P18047. Catch the Monster

Catch the Monster

Catch the Monster

给定一个有 nn 个顶点、mm 条边的森林,顶点编号为 1,2,…,n1,2,\ldots,n。森林是无环的无向图,可以不连通。

怪物最初藏在其中某个未知顶点。你可以反复执行下列操作:

  1. 选择一个顶点 xx。
  2. 若怪物当前就在 xx,则立即抓住它。
  3. 否则,这次操作未能抓住怪物。随后怪物可以停留在原地,也可以沿一条边移动到相邻顶点,但不能移动到本次选择的顶点 xx。

若存在一个预先确定的有限顶点序列,使得按此序列进行操作,无论怪物最初在哪里、每次如何移动,都能保证抓住怪物,则称这个森林是可捕获的。

共有 qq 个询问,每次给出 [l,r][l,r]。只保留编号在此区间内的顶点以及两端都保留下来的边,形成诱导子森林。判断该子森林是否可捕获。询问相互独立,怪物也只能在该次询问的子森林中活动。

输入格式

第一行三个整数 n,m,qn,m,q。

接下来 mm 行,每行两个不同的顶点 u,vu,v,表示一条无向边。保证输入图是森林。

接下来 qq 行,每行两个整数 l,rl,r。

输出格式

每个询问输出一行:若可捕获,输出 Yes;否则输出 No。

本 Hydro 版本采用默认文本比较,请按上述大小写输出 Yes 或 No。

数据范围

2≤n≤1062\le n\le10^6,1≤m≤n−11\le m\le n-1,1≤q≤1061\le q\le10^6,1≤u,v≤n1\le u,v\le n,u≠vu\ne v,1≤l≤r≤n1\le l\le r\le n。

样例 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