25376번 - 이상한 스위치

스위치는 켜져 있는 상태와 꺼져 있는 상태로 존재한다. 여러분은 꺼져 있는 스위치만 눌러 스위치를 켤 수 있다. 켜져 있는 스위치를 직접 끌 수 없음에 유의하자.

그런데, 회로를 잘못 연결해버린 나머지 어떤 스위치를 직접 켤 때, 해당 스위치가 영향을 주는 다른 스위치들의 상태는 모두 반전된다. 즉, 영향을 받는 스위치는 켜져 있었다면 꺼지고, 꺼져있었다면 켜진다. 영향을 받아 간접적으로 켜지는 스위치는 직접 켜지는 스위치가 아니다.

스위치마다 영향을 주는 스위치의 목록이 주어지고 각 스위치의 초기 상태가 주어질 때, 모든 스위치를 켜기 위해 스위치를 눌러야 하는 최소 횟수를 출력하자.

첫째 줄에 스위치의 개수 $N$이 주어진다.

둘째 줄에 $i$번째 스위치의 초기 상태 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. ($A_i=0$이면 꺼진 상태이고, $A_i=1$이면 켜진 상태이다.)

셋째 줄부터 $N$개의 줄에 걸쳐 $i$번째 스위치가 영향을 주는 스위치의 개수 $C_i$와 목록 $B_{i,1}, B_{i,2}, \cdots, B_{i,C_i}$이 공백으로 구분되어 주어진다.

모든 스위치를 켜기 위해 스위치를 눌러야 하는 최소 횟수를 출력한다. 모든 스위치를 켤 방법이 없다면, $-1$을 출력한다.

• $3 \leq N \leq 20$
• $A_i=0$ 또는 $A_i = 1$
• $0 \leq C_i \lt N$
• $1 \leq j \leq C_i$인 모든 $j$에 대해서, $1 \leq B_{i,j} \leq N$, $B_{i,j} \neq i$를 만족하고, 배열 $B_i$ 내의 값은 모두 다르다.
• 입력으로 주어지는 모든 수는 정수이다.