완벽한 선거!

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

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