Game

题意翻译

F和R喜欢玩电脑游戏。F最近发现了一个新游戏，R也觉得很有趣。 这个游戏包括n个部分，而为了完成某个部分，可能需要先完成其它的几个部分。 我们知道这个游戏总是能够完成的，也就是说，它的各个部分之间不会发生循环依赖关系。 R有3个可以玩游戏的电脑，我们用1，2，3来给电脑编号。电脑被放置在不同的房间。 同时需要注意的是，游戏的每个部分只能在其中的一台电脑上完成。 R可以完成下面的动作： - 在某些电脑上完成某些工作，并且在任意电脑上完成任意的工作都需要花费1小时 - 从1号电脑移动到2号电脑，花费的时间是1小时 - 从1号电脑移动到3号电脑，花费的时间是2小时 - 从2号电脑移动到1号电脑，花费的时间是2小时 - 从2号电脑移动到3号电脑，花费的时间是1小时 - 从3号电脑移动到1号电脑，花费的时间是1小时 - 从3号电脑移动到2号电脑，花费的时间是2小时 帮助R找到花费最少时间完成游戏的方法。在开始的时候，R可以选择在任意电脑的位置。 ## **输入输出格式** 输入格式： 第一行包含数字$n (1 \leq n \leq 200)$，表示游戏包含$n$个部分。 下面一行包含$n$个整数，第$i$个整数 $c_i (1 \leq c_i \leq 3)$ 表示用来完成第$i$个部分的电脑的编号。 下面的$n$行用来描述游戏的每个部分。 第$i$行的第$1$个数为 $k_i (0 \leq k_i \leq n-1)$， 随后的$k_i$个不同的数$a_{i, j} (1 \leq a_{i, j} \leq n, a_{i, j} \neq i)$， 表示第$i$个部分需要依赖的其它$k_i$个部分的电脑的编号。 每行的数都是用一个空格隔开的。 你可以假设游戏的每个部分是用$1$到$n$来编号的，并且游戏的不同部分不存在循环依赖。 ## **输出格式：** 输出问题的答案 ## **说明：** 注意第二个样例：在开始游戏的时候，最好的策略是选择3号电脑的位置。 首先完成第5部分，然后到1号电脑完成第3和第4部分，然后到2号电脑完成第1和第2部分。 这样总的花费的时间是$1+1+2+1+2 = 7$

题目描述

Furik and Rubik love playing computer games. Furik has recently found a new game that greatly interested Rubik. The game consists of $ n $ parts and to complete each part a player may probably need to complete some other ones. We know that the game can be fully completed, that is, its parts do not form cyclic dependencies. Rubik has $ 3 $ computers, on which he can play this game. All computers are located in different houses. Besides, it has turned out that each part of the game can be completed only on one of these computers. Let's number the computers with integers from $ 1 $ to $ 3 $ . Rubik can perform the following actions: - Complete some part of the game on some computer. Rubik spends exactly $ 1 $ hour on completing any part on any computer. - Move from the 1-st computer to the 2-nd one. Rubik spends exactly $ 1 $ hour on that. - Move from the 1-st computer to the 3-rd one. Rubik spends exactly $ 2 $ hours on that. - Move from the 2-nd computer to the 1-st one. Rubik spends exactly $ 2 $ hours on that. - Move from the 2-nd computer to the 3-rd one. Rubik spends exactly $ 1 $ hour on that. - Move from the 3-rd computer to the 1-st one. Rubik spends exactly $ 1 $ hour on that. - Move from the 3-rd computer to the 2-nd one. Rubik spends exactly $ 2 $ hours on that. Help Rubik to find the minimum number of hours he will need to complete all parts of the game. Initially Rubik can be located at the computer he considers necessary.

输入输出格式

输入格式

The first line contains integer $ n $ $ (1<=n<=200) $ — the number of game parts. The next line contains $ n $ integers, the $ i $ -th integer — $ c_{i} $ $ (1<=c_{i}<=3) $ represents the number of the computer, on which you can complete the game part number $ i $ . Next $ n $ lines contain descriptions of game parts. The $ i $ -th line first contains integer $ k_{i} $ $ (0<=k_{i}<=n-1) $ , then $ k_{i} $ distinct integers $ a_{i,j} $ $ (1<=a_{i,j}<=n; a_{i,j}≠i) $ — the numbers of parts to complete before part $ i $ . Numbers on all lines are separated by single spaces. You can assume that the parts of the game are numbered from 1 to $ n $ in some way. It is guaranteed that there are no cyclic dependencies between the parts of the game.

输出格式

On a single line print the answer to the problem.

输入输出样例

输入样例 #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

说明

Note to the second sample: before the beginning of the game the best strategy is to stand by the third computer. First we complete part 5. Then we go to the 1-st computer and complete parts 3 and 4. Then we go to the 2-nd computer and complete parts 1 and 2. In total we get 1+1+2+1+2, which equals 7 hours.