5787 - 奇怪的电视

小明过年的时候去姥姥家,除夕之夜,大家都想看春节联欢晚会,而可以依赖的就是一台旧电视。

那一台旧电视不是遥控器控制的,上面有许多按钮。按下某一按钮,其他按钮都将被释放,只有被按的按钮工作(如果其他按钮本来就是释放状态,那么它们保持不变,这对下文依旧适用)。可是当小明到来的那一天,上面的许多按钮突然无法正常工作,现在按下某个按钮后,有一些按钮将被释放,而另外的一些按钮将不改变原状态。

经过一番惨无人道的折腾,小明知道按下每一个按钮会产生什么样的效果。现在他只需要第3个按钮正常工作。

编写程序帮助小明计算,从给定的状态到只有按钮3工作而其他按钮都被释放这个最终状态所需按下的按钮序列的最短长度。

输入

第1行包含1个整数N,表示电视机的按钮数。

第2行包含用1个空格隔开的N个二进制数,表示各按钮的初始状态,0表示相应的按钮是释放的,1表示相应的按钮是按下的。

接下来的N行,表示按下某个按钮时将有哪些按钮被释放。第M+2行由数字K开头,紧跟着K个数字(按升序排列),表示当按下按钮M时被释放的按钮数及按钮号码(按钮号码用数字1~M表示),每个按钮不能释放其本身,也可能不释放任何按钮。

输入数据保证有解。

输出

输出一行一个数,必须包含从给定的状态到只有按钮3工作而其他按钮都被释放这个最终状态所需按下的按钮序列的最短长度。

样例

输入

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

输出

3

提示

【数据规模】

对于30%的数据满足:n≤10。

对于100%的数据满足:3≤n≤20。

来源

课课通

时间限制 1 秒
内存限制 256 MB
讨论 统计
上一题 下一题