미로 속의 원숭이와 바나나

배고픈 원숭이가 바나나를 먹으려고 한다. 원숭이와 바나나는 방과 그것들을 잇는 복도로 이루어진 미로 안에 있다. 각 방은 잠김(locked) 또는 열림(unlocked) 두 상태 중 하나이다. 방이 잠겨 있으면 원숭이는 그 방으로 들어갈 수 없지만, 그 방에서 나올 수는 있다. 열린 방은 자유롭게 드나들 수 있다.

일부 방에는 스위치가 있다. 스위치를 누르면 미리 정해진 방들의 집합의 상태가 한꺼번에 반전된다. 즉, 그 집합에 속한 잠긴 방은 열리고, 열린 방은 잠긴다. 같은 스위치는 항상 같은 방들의 집합의 상태를 바꾼다.

스위치가 있는 방에 들어가면, 원숭이는 원한다면 그 스위치를 누를 수 있다.

원숭이가 바나나가 있는 방을 가능한 한 빨리 찾도록, 즉 필요하다면 스위치를 누르면서 지나가야 하는 복도의 최소 개수를 구하는 프로그램을 작성하라.

입력으로 미로의 방과 복도, 모든 방의 초기 상태, 스위치 목록, 그리고 각 스위치가 상태를 바꾸는 방들의 목록이 주어진다.

첫째 줄에 방의 총 개수 N (1 ≤ N ≤ 100)과 스위치의 개수, 즉 스위치가 있는 방의 개수 S (1 ≤ S ≤ 8)가 주어진다. 스위치는 번호가 1부터 S까지인 방에 있다.

다음 N개의 줄에는 각 방의 정보가 주어진다. i번째 방의 정보는 (i+1)번째 줄에 주어지며, 그 방이 처음에 열려 있으면 0, 잠겨 있으면 1로 시작한다. 이어서 그 방과 복도로 연결된 방의 개수 K가 주어지고, 그 뒤에 연결된 K개의 방 번호가 주어진다. 같은 줄의 수들은 공백으로 구분된다.

그다음 S개의 줄에는 첫 번째부터 S번째 스위치까지의 정보가 순서대로 주어진다. 각 줄은 그 스위치가 상태를 바꾸는 방들의 개수 L로 시작하고, 이어서 그 방들의 번호 L개가 주어진다.

마지막 줄에는 두 정수 A와 B가 주어진다. A는 원숭이가 바나나를 찾기 시작하는 방의 번호이고, B는 바나나가 있는 방의 번호이다.

원숭이가 바나나를 찾기 위해 지나가야 하는 복도의 최소 개수를 한 줄에 출력한다.

참고: 모든 입력에는 항상 해가 존재한다. 즉, 방 A에서 방 B로 가는 방법이 반드시 존재한다.