← 返回题目列表

Codeforces · 213/A

A. 游戏

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

Furik 和 Rubik 喜欢玩电脑游戏。 Furik 最近发现了一款​​令 Rubik 非常感兴趣的新游戏。游戏由 n 个部分组成,为了完成每个部分,玩家可能需要完成其他一些部分。我们知道游戏是可以完全完成的,即它的各个部分不形成循环依赖。

Rubik有3台电脑,他可以在这3台电脑上玩这个游戏。所有计算机都位于不同的房子里。此外,事实证明,游戏的每个部分只能在其中一台计算机上完成。让我们用 1 到 3 的整数给计算机编号。 Rubik 可以执行以下操作:

- 在某台计算机上完成游戏的某些部分。 Rubik 在任何计算机上完成任何部分都需要花费整整 1 个小时。
- 从第一台计算机移动到第二台计算机。 Rubik 整整花了 1 个小时。
- 从第一台计算机移动到第三台计算机。 Rubik 整整花了 2 个小时。
- 从第二台计算机移至第一台计算机。 Rubik 整整花了 2 个小时。
- 从第二台计算机移至第三台计算机。 Rubik 整整花了 1 个小时。
- 从第三台计算机移至第一台计算机。 Rubik 整整花了 1 个小时。
- 从第三台计算机移至第二台计算机。 Rubik 整整花了 2 个小时。

帮助 Rubik 找到完成游戏所有部分所需的最少小时数。最初,鲁比克可以找到他认为必要的计算机。

输入

第一行包含整数 n (1 ≤ n ≤ 200) — 游戏部分的数量。下一行包含n个整数,第i个整数——ci(1≤ci≤3)代表计算机的编号,在该计算机上可以完成第i个游戏部件。

接下来的 n 行包含游戏部件的描述。第 i 行首先包含整数 ki (0 ≤ ki ≤ n - 1),然后包含 ki 个不同的整数 ai, j (1 ≤ ai, j ≤ n; ai, j ≠ i) — 第 i 部分之前要完成的部分数量。

所有行上的数字均以单个空格分隔。您可以假设游戏的各个部分以某种方式从 1 到 n 进行编号。确保游戏各部分之间不存在循环依赖关系。

输出

在一行上打印问题的答案。

示例

输入 #1

1
1
0

输出 #1

1

输入 #2

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

输出 #2

7

注意

第二个示例的注意事项:在游戏开始之前,最好的策略是站在第三台计算机旁边。首先我们完成第 5 部分。然后我们到第一台计算机完成第 3 和 4 部分。然后我们到第二台计算机完成第 1 和 2 部分。总共我们得到 1+1+2+1+2,等于 7 小时。