← 返回题目列表

Codeforces · 1423/L

L. 灯开关

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

Nikola 拥有一个大型仓库,由 $$$N$$$ 灯泡照明,编号为 $$$1$$$ 至 $$$N$$$。仓库出口处有$$$S$$$电灯开关,编号为$$$1$$$到$$$S$$$。每个开关都会交换一些灯泡的开/关状态,因此,如果灯泡关闭,翻转开关会将其打开,如果灯泡打开,翻转开关会将其关闭。

一天结束时,尼古拉想关掉所有的灯。为了实现这一目标,他将打开仓库出口处的一些电灯开关,但由于尼古拉很懒,他想打开关闭所有灯所需的_最少_个开关。由于尼古拉无法计算出最少的开关次数,因此他请你帮助他。在 $$$D$$$ 天的时间里,尼古拉在每天结束时记录了哪些灯泡关闭了,哪些灯泡打开了。他希望你告诉他在 $$$D$$$ 的每一天中需要打开多少个开关才能关闭所有灯,或者告诉他这是不可能的。

输入

第一行包含三个整数,$$$N$$$、$$$S$$$ 和 $$$D$$$ ($$$1 \leq N \leq 10^3$$$、$$$1 \leq S \leq 30$$$、$$$1 \leq D \leq 10^3$$$) – 代表灯泡数量、电灯开关数量和数量分别为天数。

接下来的 $$$S$$$ 行包含每个灯开关的描述,如下所示: 该行中的第一个数字 $$$C_i$$$ ($$$1 \leq C_i \leq N$$$) 代表灯开关 $$$i$$$ 交换开/关状态的灯泡数量,接下来的 $$$C_i$$$ 数字(按升序排列)代表索引那些灯泡。

接下来的 $$$D$$$ 行包含每天灯泡的描述,如下所示: 该行中的第一个数字 $$$T_i$$$ ($$$1 \leq T_i \leq N$$$) 表示在一天结束时打开的灯泡数量 $$$i$$$,接下来的 $$$T_i$$$ 数字(按升序排序)表示这些灯泡的索引灯泡。

输出

打印 $$$D$$$ 行,每天一行。在 $$$i^{th}$$$ 行中,打印 $$$i$$$ 当天需要打开的开关的最少数量,如果无法关闭所有灯,则打印 $$$-1$$$。

示例

输入 #1

4 3 4
2 1 2
2 2 3
1 2
1 1
2 1 3
3 1 2 3
3 1 2 4

输出 #1

2
2
3
-1