A. Игра
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Фурик и Рубик любят играть в компьютерные игры. Недавно Фурик нашел новую игру, которая очень заинтересовала Рубика. Игра состоит из n частей, причем для прохождения каждой части, возможно, требуется пройти некоторые другие. Известно, что игру можно пройти полностью, то есть нет циклических зависимостей между частями игры.

У Рубика есть 3 компьютера, на которых он может играть в эту игру. Все компьютеры находятся в разных домах и, как оказалось, каждую часть игры можно пройти только на одном из этих компьютеров. Пронумеруем компьютеры целыми числами от 1 до 3. Рубик может выполнять следующие действия:

  • Пройти какую-то часть игры на каком-то компьютере. Рубик тратит на прохождение любой части на любом компьютере ровно 1 час.
  • Переместиться от 1-го компьютера ко 2-му. На это действие Рубик тратит ровно 1 час.
  • Переместиться от 1-го компьютера к 3-му. На это действие Рубик тратит ровно 2 часа.
  • Переместиться от 2-го компьютера к 1-му. На это действие Рубик тратит ровно 2 часа.
  • Переместиться от 2-го компьютера к 3-му. На это действие Рубик тратит ровно 1 час.
  • Переместиться от 3-го компьютера к 1-му. На это действие Рубик тратит ровно 1 час.
  • Переместиться от 3-го компьютера ко 2-му. На это действие Рубик тратит ровно 2 часа.

Помогите Рубику найти минимальное количество часов, которое ему понадобится для прохождения всех частей игры. Изначально Рубик может находиться у компьютера, который он считает нужным.

Входные данные

В первой строке задано целое число 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
0
Выходные данные
1
Входные данные
5
2 2 1 1 3
1 5
2 5 1
2 5 4
1 5
0
Выходные данные
7
Примечание

Пояснение ко второму примеру: перед началом игры выгоднее всего находиться у 3-го компьютера. Сначала пройдем часть номер 5. Далее перейдем к 1-му компьютеру и пройдем 3-ю и 4-ю часть. Далее перейдем ко 2-му компьютеру и пройдем 1-ю и 2-ю часть. В сумме получаем 1+1+2+1+2, что равно 7 часам.