Survivable Diagnostic Rules

A doctor has a list of rules for judging whether a patient can survive. Each rule consists of two states, and if both states are true at the same time, the patient is judged to die.

Each symptom can either be observed or not observed. If it is possible to choose one state for every symptom so that no rule has both of its states true, then such a patient can survive.

Given the rule list, determine whether there exists a combination of symptom states that can survive.

The input consists of several test cases. The first line of each test case contains two integers N and M, the number of rules and the number of symptom types.

Each of the next N lines contains two integers describing one rule. The absolute value of each integer is a symptom number between 1 and M. A positive integer x means that symptom x is observed, while a negative integer -x means that symptom x is not observed. If the two states on the same line are both true, the patient dies.

The input ends with 0 0. When both N and M are 0, stop processing.

The limits are N <= 200,000 and M <= 20,000.

For each test case, print 1 if there exists a survivable combination of states, and print 0 otherwise.