Perfect Election!

In some country (I can't remember which), candidates ${1, 2, \ldots, N}$ are running in a parliamentary election. In a poll, each person was asked: "For two candidates $i$ and $j$, what election outcome for those two would make you happy?" The possible answers and their input formats are shown in the table below, and $i$ and $j$ may be equal.

We have a list of $M$ possible answers, and some of these $M$ answers may be similar or identical. If there is an election outcome that satisfies all $M$ answers at the same time, we call that outcome perfect. (Note that candidates ${1, 2, \ldots, N}$ may all be elected, all be defeated, or only some of them elected!)

Your task is to print 1 if a perfect election outcome exists for the $M$ answers, and 0 otherwise.

Each test case begins with two numbers $N$ and $M$ ($1 \le N \le 1000$, $1 \le M \le 1000000$). Then $M$ pairs of the form $\pm i\ \pm j$ follow ($1 \le i, j \le N$). Each pair is interpreted according to the table above.

All input values are separated by whitespace, and the input ends at end of file (EOF).

For each test case, print whether a perfect election outcome exists: print 1 if it does and 0 otherwise. Print one result per line, and do not print any blank lines between results.

For example, with three candidates and the opinions +1 +2, -1 +2, -1 -3, a perfect outcome exists (there are several; electing only candidate 2 is one of them), so the answer is 1.

With two candidates and the opinions -1 +2, -1 -2, +1 -2, +1 +2, no perfect outcome exists, so the answer is 0: -1 +2 and -1 -2 require candidate 1 not to be elected, while +1 -2 and +1 +2 require candidate 1 to be elected.

Similar or identical opinions may be mixed together without changing the result.