소등

이브는 거의 언제나 사무실에 마지막까지 남는다. 이브는 어두운 곳을 무서워하는데, 회사 규칙상 마지막으로 나가는 사람이 사무실의 모든 램프가 꺼졌는지 확인해야 한다. 동료는 자기 방 램프를 끄지 않고 퇴근할 때가 많다.

사무실의 각 방에는 램프가 정확히 하나씩 있고, 스위치는 여러 개 있을 수도 있다. 이 스위치는 보통 스위치와 다르다. 스위치마다 상태를 뒤집는 램프 집합이 정해져 있고, 스위치를 누르면 그 집합에 속한 램프의 상태가 모두 뒤집힌다. 켜져 있던 램프는 꺼지고, 꺼져 있던 램프는 켜진다. 스위치가 놓인 방의 램프가 그 집합에 들어 있지 않을 수도 있고, 스위치가 하나도 없는 방도 있다.

이브는 매일 저녁 같은 경로로 사무실을 나서려고 한다. 그런데 켜져 있는 램프의 조합은 날마다 다르므로 어떤 경우에도 통하는 경로를 정해야 한다. 즉 켜진 램프가 어떤 상태이든, 경로가 지나는 방의 스위치를 적절히 조합해 모든 램프를 끌 수 있어야 한다.

애초에 끌 수 없는 상태도 있다. 예를 들어 램프 하나만 켜진 상태를 끄지 못하는 경우가 있다. 그런 상태는 켤 수도 없으므로 이브가 신경 쓸 필요는 없다. 경로는 실제로 끌 수 있는 상태만 처리하면 된다.

이브는 불 꺼진 방을 지나가도 괜찮다. 마지막 램프가 경로 중간에 꺼져서 남은 구간을 어두운 방으로 걸어도 상관없다.

첫째 줄에 방의 수 $n$, 방 사이 통로의 수 $m$, 스위치의 수 $l$이 주어진다 ($2 \le n \le 20$, $1 \le m \le 190$, $1 \le l \le 100$).

다음 $m$개의 줄에는 서로 오갈 수 있는 두 방의 번호 $a$와 $b$가 주어진다 ($a \ne b$). 같은 방 쌍 $\{a, b\}$는 두 번 이상 주어지지 않는다.

다음 $l$개의 줄에는 스위치가 하나씩 주어진다. 각 줄은 스위치가 있는 방의 번호로 시작한다. 두 번째 정수 $p$ ($p > 0$)는 그 스위치가 상태를 뒤집는 램프의 개수이고, 이어서 그 램프가 있는 방의 번호 $p$개가 주어진다. 한 스위치의 목록에 같은 방 번호가 두 번 나오지는 않는다.

방 번호는 $0$부터 $n-1$까지이다. 이브가 사무실을 나가는 방은 $0$번이고, 이브가 출발하는 방은 $1$번이다. $1$번 방에서 모든 방으로 갈 수 있다.

이브의 방에서 출구 방까지 가는 경로 가운데, 그 경로가 지나는 방의 스위치만으로 끌 수 있는 램프 상태를 모두 끌 수 있는 경로를 찾는다. 그런 경로가 지나는 방의 개수의 최솟값을 한 줄에 출력한다. 양 끝 방도 센다. 같은 방을 여러 번 지나면 지날 때마다 센다.