완벽한 선거!

시간 제한3초메모리 제한256 MB

요약

후보들의 당선 여부에 대한 불리언 절 조건들이 주어질 때, 모든 조건을 만족하는 선거 결과가 존재하는지 판별합니다.

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

문제

어떤 나라에서는(어느 나라인지는 기억이 안 나지만) 후보 $\{1, 2, \ldots, N\}$ 이 나와서 국회의원 선거를 치르고 있다. 여론조사에서는 사람들에게 "두 후보 $i$ , $j$ 에 대해, 그 두 후보의 선거 결과가 어떻게 나오면 행복할 것 같으세요?"라고 물어봤다. 이 질문에 대한 가능한 답변과 입력 양식은 아래 표에 나와 있으며, $i$ 와 $j$ 는 같을 수도 있다.

여론조사에서 가능한 답변	입력 양식
나는 $i$ 와 $j$ 둘 중 적어도 한 명은 당선되면 좋겠어.	`+i +j`
나는 $i$ 와 $j$ 둘 중 적어도 한 명은 떨어지면 좋겠어.	`-i -j`
나는 $i$ 가 붙거나 $j$ 가 떨어지거나, 둘 다면 좋겠어.	`+i -j`
나는 $j$ 가 붙거나 $i$ 가 떨어지거나, 둘 다면 좋겠어.	`-i +j`

우리는 $M$ 개의 가능한 답변 목록을 가지고 있고, 이 $M$ 개의 답변 중 비슷하거나 동일한 것이 있을 수도 있다. 만약 이 $M$ 개의 답변을 동시에 만족하는 선거 결과가 있다면, 그 선거 결과를 완벽하다고 한다. (다만 후보 $\{1, 2, \ldots, N\}$ 이 모두 당선될 수도, 모두 낙선될 수도, 일부만 당선될 수도 있다!)

우리가 할 일은 $M$ 개의 답변에 대해 완벽한 선거 결과가 있으면 1을, 아니면 0을 출력하는 것이다.

입력

각 테스트 케이스는 두 수 $N$ 과 $M$ 을 입력받으며 시작한다( $1 \le N \le 1000$ , $1 \le M \le 1000000$ ). 이어서 $\pm i\ \pm j$ 형태의 순서쌍 $M$ 개가 주어진다( $1 \le i, j \le N$ ). 각 순서쌍은 위 표대로 해석하면 된다.

각 입력 값은 공백으로 구분되며, 입력의 끝에는 EOF(파일의 끝)가 주어진다.

출력

각 테스트 케이스에 대해 완벽한 선거 결과가 존재하는지 출력한다. 존재하면 1을, 아니면 0을 출력한다. 결과는 매 줄마다 하나씩 출력하며, 결과 사이에 빈 줄이 있어서는 안 된다.

노트

예를 들어 후보가 셋이고 답변이 +1 +2, -1 +2, -1 -3이면 완벽한 결과가 존재하므로(여러 가지가 있는데, 후보 2만 당선되는 경우가 그 하나다) 답은 1이다.

후보가 둘이고 답변이 -1 +2, -1 -2, +1 -2, +1 +2이면 완벽한 결과가 존재하지 않으므로 답은 0이다. -1 +2와 -1 -2는 후보 1이 당선되면 안 된다고 요구하지만, +1 -2와 +1 +2는 후보 1이 당선되어야 한다고 요구하기 때문이다.

비슷하거나 동일한 답변이 섞여 있어도 결과는 달라지지 않는다.

예제3

예제 1

입력

3 3  +1 +2  -1 +2  -1 -3
2 3  -1 +2  -1 -2  +1 -2
2 4  -1 +2  -1 -2  +1 -2  +1 +2
2 8  +1 +2  +2 +1  +1 -2  +1 -2  -2 +1  -1 +1  -2 -2  +1 -1

예상 출력

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