시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 147 35 20 50.000%

문제

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

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

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

입력

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

셋째 줄부터 M개의 줄에는 스위치와 연결된 방의 정보가 주어진다. 스위치와 연결된 방의 정보는 총 k+1개의 정수로 이루어져 있고, 첫 정수는 연결된 방의 개수이고, 나머지 정수는 연결된 방의 정보이다.

출력

모든 방을 열 수 있으면 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

출처