생존 가능한 진단 규칙

한 의사는 환자의 여러 증세를 관찰해 생존 가능성을 판단하는 규칙 목록을 가지고 있다. 각 규칙은 두 가지 상태로 이루어져 있으며, 그 두 상태가 동시에 만족되면 환자는 사망한다고 판단한다.

하나의 증세에는 관측되는 상태와 관측되지 않는 상태가 있다. 모든 증세에 대해 관측 여부를 하나씩 정했을 때, 어떤 규칙의 두 상태도 동시에 만족되지 않는다면 그 환자는 살아남을 수 있다.

규칙 목록이 주어질 때, 살아남을 수 있는 증세 상태의 조합이 존재하는지 판별하시오.

입력은 여러 개의 테스트 데이터로 이루어져 있다. 각 테스트 데이터의 첫 줄에는 규칙의 개수 N과 증세의 종류 수 M이 공백으로 구분되어 주어진다.

다음 N개의 줄에는 규칙 하나를 나타내는 두 정수가 주어진다. 각 정수의 절댓값은 증세 번호이며 1 이상 M 이하이다. 양수 x는 x번 증세가 관측되는 상태를 뜻하고, 음수 -x는 x번 증세가 관측되지 않는 상태를 뜻한다. 한 줄의 두 상태가 동시에 만족되면 환자는 사망한다.

입력의 끝은 0 0으로 주어진다. N과 M이 모두 0이면 입력을 종료한다.

제한은 N <= 200,000, M <= 20,000이다.

각 테스트 데이터마다 살아남을 수 있는 상태 조합이 존재하면 1, 존재하지 않으면 0을 한 줄에 출력한다.