问题 5586 --圣诞树彩灯

5586: 圣诞树彩灯

时间限制: 3 Sec  内存限制: 1024 MB
提交: 2  解决: 2
[提交][状态][命题人:]

题目描述

圣诞节布置圣诞树时,会添加一些发光的彩灯,增加圣诞树的颜值。

现在圣诞树上有 n 个灯泡,编号为 1~n ,并且有 s 个开关控制这些彩灯。第 i 个开关会影响 c[i] 个不同的彩灯 a[i][1],a[i][2],...,a[i][c[i]] 。每当切换开关时,受影响的彩灯均会改变灯泡的发光情况。若灯泡原先发光,则变为熄灭;反之若灯泡原先熄灭,则变为发光。

现在有一些灯泡熄灭了,你需要用最少的操作开关次数,让所有灯泡发光。
共有 q 次询问,每次询问给定熄灭的灯泡编号,其他灯泡均发光。对于每次询问,求最少操作次数。若无法使得所有灯泡均发光,则输出 -1 。

输入

第一行输入三个整数 n,s,q (1≤n≤10^3, 1≤s≤30, 1≤q≤10^3) ,分别表示灯泡数、开关数、询问数。
接下来 s 行,第 i 行表示第 i 个开关所影响的灯泡。首先包含一个整数 c[i] ,表示受影响的灯泡数,接下来 c[i] 个不同的递增整数,表示灯泡编号。
接下来 q 行,每行表示一个询问。首先包含一个整数 t ,表示熄灭的灯泡数,接下来 t 个不同的递增整数,表示灯泡编号。

输出

对于每组询问,输出一行,包含一个整数,表示最小操作数。若无合法方案,则输出-1。
样例输入
Copy
4 3 4
2 1 2
2 2 3
1 2
1 1
2 1 3
3 1 2 3
3 1 2 4
样例输出
Copy
2
2
3
-1

提示

来源

[提交][状态]