시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 198 58 38 48.101%

문제

구사과 호텔에는 총 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을 출력한다.

예제 입력 1

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

예제 출력 1

0

예제 입력 2

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

예제 출력 2

1

예제 입력 3

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

예제 출력 3

0

출처