CF639F Bear and Chemistry

Limak 是一只聪明的棕熊，他喜欢化学、反应和元素变换。 在 Bearland（Limak 的家）中有 $n$ 种元素，编号为 $1$ 到 $n$。这里还有一些特殊机器，可以用来变换元素。每台机器由两个整数 $a_{i},b_{i}$ 描述，分别代表两种元素（不一定不同）。一台机器可以把元素 $a_{i}$ 变成 $b_{i}$，也可以把 $b_{i}$ 变成 $a_{i}$。Bearland 的机器不太耐用，每台机器最多只能使用一次。也有可能 $a_{i} = b_{i}$，并且可能有很多台机器的对 $(a_{i},b_{i})$ 是一样的。 Radewoosh 是 Limak 最大的敌人兼对手。他想考验 Limak 的化学知识。他们将在明天见面，并各自带上所有的机器。Limak 拥有 $m$ 台机器，但他对自己的敌人了解不多。他们约定：Radewoosh 将会选择两个不同的元素，记作 $x$ 和 $y$。Limak 可以使用他自己的机器和 Radewoosh 的机器，每台机器使用次数最多一次。Limak 将从元素 $x$ 开始，他的任务是先变得到元素 $y$，再变回元素 $x$——这样就算成功。然后 Radewoosh 就会承认 Limak 懂化学了（然后就离开）。 Radewoosh 有一个自己喜欢的「非空元素集合」，他会从这个集合中选择 $x,y$。Limak 并不确切知道这个集合里有哪些元素，也不知道 Radewoosh 拥有什么机器。不过 Limak 听说了 $q$ 个流言，每个流言包含了 Radewoosh 拥有的机器和他喜欢的元素集合。对于每个流言，Limak 想知道：无论 $x,y$ 取自给定集合中的哪一对不同元素，他都能完成任务吗？如果可以，输出 "YES"；如果存在某一对 $x,y$ 使得 Limak 无法完成任务，则输出 "NO"。

第一行包含三个整数 $n$、$m$ 和 $q$（$1 \leq n, q \leq 300000, 0 \leq m \leq 300000$），分别表示元素数量、Limak 机器数量和流言数量。 接下来 $m$ 行，每行两个整数 $a_{i}, b_{i}$（$1 \leq a_{i}, b_{i} \leq n$），表示 Limak 的一台机器。 接下来是 $q$ 个流言的描述。 第 $i$ 个流言的第一行有两个整数 $n_{i}, m_{i}$（$1 \leq n_{i} \leq 300000, 0 \leq m_{i} \leq 300000$）。第二行为 $n_{i}$ 个互不相同的整数 $x_{i,1}, x_{i,2}, \ldots, x_{i,n_i}$（$1 \leq x_{i,j} \leq n$），表示该流言中 Radewoosh 喜爱的元素集合。注意当 $n_{i} = 1$ 时，没有不同元素对，Limak 自动获胜（输出 "YES"）。 随后有 $m_{i}$ 行，每行两个整数 $a_{i,j}, b_{i,j}$（$1 \leq a_{i,j}, b_{i,j} \leq n$），描述流言中 Radewoosh 的机器。 重要提示：为了实现在线查询，每一个在输入中出现的元素或机器对 $(a, b)$ 都需要通过如下函数进行映射： ```cpp int rotate(int element) { element=(element+R)%n; if (element==0) { element=n; } return element; } ``` 其中 $R$ 初始为 $0$，每次若该查询的答案为 "YES"，则 $R$ 增加本次查询的编号。查询编号从 $1$ 开始，按输入顺序编号。

你应输出 $q$ 行，第 $i$ 行输出 "YES"（不带引号）当第 $i$ 个流言中，对于所有 $x, y$（取自该流言的喜欢集合且 $x \neq y$）Limak 都可以完成任务；否则输出 "NO"（不带引号）。

我们来看第一个样例： 第一个流言 Radewoosh 喜欢的元素集合是 $\{4,2\}$，没有机器。Limak 可以把元素 $4$ 变成 $2$（任务一半完成），再把 $2$ 变成 $3$，$3$ 变成 $4$。答案是 "YES"，所以 $R$ 增加 $1$。 第二个流言，输入集合为 $\{6,2\}$，机器为 $(3,4)$，但此时 $R = 1$，所以集合实际为 $\{1,3\}$，机器为 $(4,5)$。答案是 "NO"，$R$ 不变。 第三个流言集合 $\{6,4,3\}$ 和机器 $(2,5)$、$(4,6)$ 被映射为 $\{1,5,4\}$，机器为 $(3,6)$ 和 $(5,1)$。 假设 Radewoosh 选择： - 如果选择 $1$ 和 $5$，Limak 可以 $1\to 5, 6\to 3, 3\to 2, 2\to 1$。 - 如果选择 $5$ 和 $4$，Limak 可以 $5\to 6, 6\to 3, 3\to 4$（一半已完成），$4\to 2, 2\to 1, 1\to 5$。 - 如果选择 $1$ 和 $4$，Limak 可以 $1\to 2, 2\to 4, 4\to 3, 3\to 6, 6\to 5, 5\to 1$。 因此 Limak 能完成任务。答案为 "YES"，$R$ 增加 $3$（此时为 $4$）。 最后一条流言 $\{1,2\}$ 和机器 $(1,2)$ 将被映射为 $\{5,6\}$ 和 $(5,6)$。现在有两台 $(5,6)$ 的机器，Limak 能完成任务。因此输出 "YES"。 由 ChatGPT 5 翻译