호텔 관리

면접 대비

시간 제한2초메모리 제한512 MB

요약

방마다 스위치 두 개가 연결되어 있을 때, 일부 스위치를 눌러 모든 방을 열 수 있는지 판별한다.

난이도: 보통10점 중 6점
유형: 그래프, DFS, 유니온 파인드, 비트 연산
정답자: 아직 제출이 없습니다

문제

구사과 호텔에는 총 N개의 방이 있고, 방의 잠금 상태를 제어하는 스위치가 M개 있다. 모든 방은 두 개의 스위치와 연결되어 있다.

초기 방의 잠금 상태가 주어질 때, 스위치를 이용해 모든 방을 열려고 한다. 스위치를 누르면 연결된 방의 상태가 반전된다. 예를 들어, 방 1, 2, 3의 상태가 열림, 닫힘, 열림이고, 세 방이 모두 스위치 1과 연결되어 있는 경우에 이 스위치를 누르면 방의 상태가 닫힘, 열림, 닫힘이 된다.

스위치를 이용해 모든 방을 열 수 있는지 알아보자.

입력

첫째 줄에 방의 개수 N(2 ≤ N ≤ 100,000)과 스위치의 개수 M(2 ≤ M ≤ 100,000)이 주어진다. 둘째 줄에는 초기 방의 잠금 상태가 1번 방부터 순서대로 주어진다. 0은 닫힌 상태, 1은 열린 상태이다.

셋째 줄부터 M개의 줄에는 스위치와 연결된 방의 정보가 주어진다. 각 스위치의 정보는 정수 K 하나와, K개의 공백으로 구분된 방 번호로 주어진다. 방 번호는 1 이상 N 이하의 정수이며, 주어지는 스위치들의 정보는 문제의 조건을 만족한다.

출력

모든 방을 열 수 있으면 1, 없으면 0을 출력한다.

예제3

예제 1
입력
```
3 3
1 0 1
2 1 3
2 1 2
2 2 3
```
예상 출력
```
0
```
예제 2
입력
```
3 3
1 0 1
3 1 2 3
1 2
2 1 3
```
예상 출력
```
1
```
예제 3
입력
```
3 3
1 0 1
3 1 2 3
2 1 2
1 3
```
예상 출력
```
0
```