P14449 [ICPC 2025 Xi'an R] Catch the Monster

一只史前怪兽通过 Peter 博士的时光机来到了地球。你需要帮助 Peter 博士抓住它。 怪兽藏在一片由 $n$ 个顶点和 $m$ 条边组成的森林中。这里的森林指的是一个无环无向图，它可能由多棵树组成。为了抓住怪兽，你可以执行以下操作： - 首先，选择一个顶点 $x$（$1 \leq x \leq n$）。 - 然后，如果怪兽此时位于顶点 $x$，它就被抓住； - 否则，怪兽仍未被抓住，并且在这次操作结束后，它可以选择移动到当前顶点相邻的任意顶点，但不能移动到顶点 $x$；或者它也可以选择不移动，停留在原地。 我们称一片森林是 **良好的**，当且仅当存在一个有限的顶点序列 $a$，无论怪兽最初位于哪个顶点、以及它之后如何移动，只要依照 $a$ 中顶点的顺序依次执行上述操作，就能保证怪兽最终一定被抓住。 现在，你需要回答来自 Peter 博士的 $q$ 个问题。在每个问题中，他会给出一个区间 $[l, r]$（$1 \leq l \leq r \leq n$）。你需要告诉他：由编号在区间 $[l, r]$ 内的顶点所诱导出的子森林（即仅保留这些顶点及其之间的边所构成的图）是否是 **良好的**。

输入的第一行包含三个整数 $n, m, q$（$2 \leq n \leq 10^6$，$1 \leq m \leq n-1$，$1 \leq q \leq 10^6$），分别表示森林中的顶点数、边数和查询次数。 接下来的 $m$ 行中，每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$，且 $u \neq v$），表示森林中的一条边。 接下来的 $q$ 行中，每行包含两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n$），表示一个查询区间。

对于每个查询，输出一行结果： - 如果该子森林是 **良好的**，输出 `Yes`； - 否则输出 `No`。 输出时不区分大小写。例如，字符串 `yEs`、`yes`、`Yes` 和 `YES` 都会被视为正确的回答。

在第一个测试用例中： - 对于第一个查询，子森林 $[1,3]$，你可以选择序列 $a = [3, 1, 2]$； - 对于第二个查询，子森林 $[2,6]$，你可以选择序列 $a = [3, 4, 5, 2, 6]$； - 对于第三个查询，子森林 $[1,10]$，可以证明不存在一个有限的有效序列 $a$。 在第二个测试用例中： - 对于唯一的查询，子森林 $[1,9999]$，你可以选择序列 $a = [1, 2, \ldots, 9999]$。 翻译由 ChatGPT-5 完成