시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB12118100.000%

문제

Dave has a TV that is quite old, and some of its switches are not functioning properly. Pressing a switch (while TV was new) released all the other switches thus leaving only one switch in pressed position.

Pressing a switch now will release some of the switches leaving the positions of other switches unchanged. Dave knows the effects of pressing every switch.

Write a program that will help Dave determine the length of the shortest sequence of switches that need to be pressed from their given position so that at the end only switch 3 is in pressed position and all the others are released.

입력

The first line of the input contains an integer N, 3 ≤ N ≤ 20, the number of TV switches.

The second line of input contains N binary digits separated by a space character determining the initial position of switches - 0 means that the corresponding switch is released, and 1 that it is in pressed position.

The next N lines of input determine the switches that are released by pressing a switch. (M+2)th line begins with a number K followed by K numbers (sorted in ascending order) - switches that are released when the switch M is pressed. (Switches are denoted by a numbers from 1 to N.) A switch cannot release itself and it is possible that a switch does not release any switch at all.

Note: Input data will be chosen so that a solution always exists.

출력

The first and only line of output should contain the length of the shortest sequence of switches that need to be pressed so that at the end only switch 3 is in pressed position and all the others are released.

예제 입력 1

3
1 1 0
2 2 3
2 1 3
2 1 2

예제 출력 1

1

예제 입력 2

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

예제 출력 2

2

예제 입력 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

3

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2004 > Regional Competition - Seniors 3번

  • 문제의 오타를 찾은 사람: doju