여물통 게임

면접 대비

시간 제한1초메모리 제한128 MB

요약

N개의 여물통과 각 질의가 나열된 부분집합 안의 채워진 개수를 알려줄 때, 채워진 집합을 찾거나 불가능 또는 유일하지 않음을 판정한다.

난이도: 보통10점 중 6점
유형: 완전 탐색, 비트 연산, 수학
정답자: 아직 제출이 없습니다

문제

농부 John과 Bessie가 또 게임을 한다. 이번에는 물이 담긴 여물통을 가지고 논다.

농부 John은 헛간 뒤에 여물통 $N$ 개 ( $1 \le N \le 20$ )를 숨겨 두고 그중 일부에 먹이를 채웠다. Bessie는 $M$ 개 ( $1 \le M \le 100$ )의 질문을 하는데, 각 질문은 “다음 목록에 있는 여물통 중 먹이가 채워진 것은 몇 개인가?” 형태이다.

어떤 여물통에 먹이가 채워져 있는지 정확히 알아내도록 Bessie를 도와라.

예를 들어 여물통이 4개이고 Bessie가 다음 네 질문을 하여 아래 답을 받았다고 하자.

여물통 {1}: 1개 채워짐
여물통 {2, 3}: 1개 채워짐
여물통 {1, 4}: 1개 채워짐
여물통 {3, 4}: 1개 채워짐

그러면 다음과 같이 추론할 수 있다.

질문 1에서 여물통 1은 채워져 있다.
여물통 1이 채워져 있으므로 질문 3에 의해 여물통 4는 비어 있다.
여물통 4가 비어 있으므로 질문 4에 의해 여물통 3은 채워져 있다.
여물통 3이 채워져 있으므로 질문 2에 의해 여물통 2는 비어 있다.

따라서 채워진 여물통은 정확히 1 0 1 0 이다.

입력

첫째 줄: 공백으로 구분된 두 정수 $N$ 과 $M$ .
둘째 줄부터 $M+1$ 번째 줄까지: 각 줄은 질문 하나를 나타낸다. 길이 $N$ 의 문자열(각 문자는 0 또는 1이며, 1은 그 질문의 목록에 포함된 여물통을 뜻한다)이 먼저 오고, 공백 하나 뒤에 그 목록에서 먹이가 채워진 여물통의 개수를 나타내는 정수 하나가 온다.

출력

한 줄을 출력한다.

농부 John의 모든 답과 일치하는 여물통 상태가 존재하지 않으면 IMPOSSIBLE.
답과 일치하는 상태가 존재하지만 유일하게 결정되지 않으면 NOT UNIQUE.
그 외의 경우, 채워진 여물통을 유일하게 나타내는 길이 $N$ 의 0/1 문자열.

예제1

예제 1
입력
```
4 4
1000 1
0110 1
1001 1
0011 1
```
예상 출력
```
1010
```