← 返回题目列表

Codeforces · 639/F

F. 熊和化学

中文机器翻译题面 查看原题

Limak 是一只聪明的棕熊,喜欢化学、反应和转化元素。

在 Bearland(Limak 的家)中,有 n 个元素,编号为 1 到 n。还有可以转换元素的特殊机器。每台机器由两个整数ai、bi描述,代表两个元素,不一定不同。人们可以使用机器将元素 ai 转换为 bi 或将 bi 转换为 ai。熊地的机器抵抗力不太强,每台机器最多只能使用一次。有可能 ai = bi 并且许多机器具有相同的 ai、bi 对。

Radewoosh 是 Limak 最大的敌人和竞争对手。他想测试利马克的化学反应。他们明天见面,两人都会带来他们所有的机器。利马克有 m 台机器,但他对敌人了解不多。他们同意 Radewoosh 将选择两个不同的元素,我们将它们表示为 x 和 y。利马克将被允许使用他和拉德伍什的机器。他可能使用零台或更多(甚至可能是全部)机器来实现目标,每台机器最多一次。 Limak 将从元素 x 开始,他的任务是首先获取元素 y,然后再次获取元素 x——然后我们说他成功了。之后拉德伍什会同意利马克知道化学反应(拉德伍什会离开)。

Radewoosh 喜欢一些特定的非空喜爱元素集,他会从该集中选择 x, y。 Limak 并不确切知道集合中有哪些元素,也不知道 Radewoosh 有哪些机器。 Limak 听过 q 条八卦(查询),每条八卦都包含 Radewoosh 的机器和最喜欢的元素。对于每个八卦,利马克想知道他是否能够在明天为从最喜欢的元素集中选择的每对 x、y 取得成功。如果是,则打印“YES”(不带引号)。但是,如果给定集合中存在一对 (x, y),Limak 无法成功,那么您应该打印“NO”(不带引号)。

输入

第一行包含三个整数 n、m 和 q (1 ≤ n, q ≤ 300 000, 0 ≤ m ≤ 300 000)——分别是元素的数量、Limak 机器的数量和八卦的数量。

接下来的 m 行中的每一行都包含两个整数 ai 和 bi (1 ≤ ai, bi ≤ n),描述 Limak 的机器之一。

接下来是q个八卦的描述。

第 i 个八卦的描述的第一行包含两个整数 ni 和 mi (1 ≤ ni ≤ 300 000, 0 ≤ mi ≤ 300 000)。第二行包含 ni 个不同的整数 xi, 1, xi, 2, ..., xi, ni (1 ≤ xi, j ≤ n)——Radewoosh 在第 i 个八卦中最喜欢的元素。请注意,允许 ni = 1,在这种情况下,不存在不同元素对,因此 Limak 自动获胜(答案是“是”)。接下来是 mi 行,每行包含两个整数 ai, j, bi, j (1 ≤ ai, j, bi, j) 描述第 i 个八卦中的 Radewoosh 机器之一。

所有八卦的 ni 总和不会超过 300 000。同时,所有八卦的 mi 总和也不会超过 300 000。

重要提示:因为我们希望您在线处理八卦,为了了解 Radewoosh 最喜欢的集合中的元素以及他的机器可以转换的元素,对于输入中表示它们的每个数字,您应该使用以下函数:

,其中 R 最初等于 0,并且只要答案为“是”,就会增加查询的数量。查询按照它们在输入中出现的顺序从 1 开始编号。

输出

你应该打印 q 行。如果对于每对元素 x 和 y(在集合 xi, 1, xi, 2, ..., xi, ni 中)的第 i 个八卦 Limak 能够成功,则其中第 i 个应该包含“YES”(不带引号)。否则你应该打印“NO”(不带引号)。

示例

输入 #1

6 5 4
1 2
2 3
3 4
2 4
5 6
2 0
4 2
2 1
6 2
3 4
3 2
6 3 4
2 5
4 6
2 1
1 2
1 2

输出 #1

YES
NO
YES
YES

输入 #2

7 6 2
1 2
1 3
2 4
2 5
3 6
3 7
7 2
1 2 3 4 5 6 7
4 5
6 7
7 2
1 2 3 4 5 6 7
4 6
5 7

输出 #2

NO
YES

注意

让我们看一下第一个示例:

在第一个八卦中,Radewoosh 最喜欢的集合是 {4, 2} 并且他没有机器。 Limak 可以将元素 4 转换为 2(这样任务就完成了一半),然后将 2 转换为 3,将 3 转换为 4。答案是“是”,因此 R 增加 1。

在第二个八卦中,输入中的集合由 {6, 2} 表示,机器由 (3, 4) 表示,但 R 等于 1,因此集合为 {1, 3},机器为 (4, 5)。答案是“否”,所以 R 没有改变。

在第三个八卦集合{6,4,3}中,机器(2,5)和(4,6)被解密为{1,5,4},(3,6)和(5,1)。

考虑 Radewoosh 的选择:

- 如果他选择元素 1 和 5,那么 Limak 能够将 1 转化为 5,然后将 6 转化为 3,将 3 转化为 2,将 2 转化为 1。
- 如果他选择元素 5 和 4,那么 Limak 能够将 5 转化为 6、6 转化为 3、3 转化为 4(已经落后他一半)、4 转化为 2、2 转化为 1、1 转化为 5。
- 如果他选择元素 1 和 4,那么 Limak 能够将 1 转化为 2、2 转化为 4、4 转化为 3、3 转化为 6、6 转化为 5 以及 5 转化为 1。

所以 Limak 能够执行任务。答案是“是”,R 增加 3(现在等于 4)。

在最后的八卦中,{1, 2} 和​​ (1, 2) 被解密为 {5, 6} 和 (5, 6)。现在有 2 台机器(5、6),因此 Limak 能够再次执行任务。