2-SAT Satisfiability

2-SAT asks how to pick a value for each of the boolean variables $x_1, x_2, \ldots, x_N$ so that a 2-CNF formula becomes true.

A 2-CNF formula looks like $(x \lor y) \land (\lnot y \lor z) \land (x \lor \lnot z) \land (z \lor y)$. Each parenthesized part is a clause, and a clause joins two variables with $\lor$. Here $\lor$ is OR, $\land$ is AND, and $\lnot$ is NOT.

You are given the number of variables $N$, the number of clauses $M$, and the formula $f$. Write a program that decides whether $f$ can be made true.

For example, take $N = 3$, $M = 4$, and $f = (\lnot x_1 \lor x_2) \land (\lnot x_2 \lor x_3) \land (x_1 \lor x_3) \land (x_3 \lor x_2)$. Setting $x_1$ to false, $x_2$ to false, and $x_3$ to true makes $f$ true. For $N = 1$, $M = 2$, and $f = (x_1 \lor x_1) \land (\lnot x_1 \lor \lnot x_1)$, no value of $x_1$ makes $f$ true.

The first line holds the number of variables $N$ ($1 \le N \le 10000$) and the number of clauses $M$ ($1 \le M \le 100000$). Each of the next $M$ lines holds one clause as two integers $i$ and $j$ ($1 \le |i|, |j| \le N$). A positive $i$ means $x_i$ and a negative $i$ means $\lnot x_{-i}$. The same rule applies to $j$.

Print 1 on the first line if $f$ can be made true, and 0 otherwise.