2-SAT smallest assignment

2-SAT asks you to choose values for the boolean variables $x_1, x_2, \dots, x_N$ so that a given 2-CNF formula is 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 part inside parentheses 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$. Decide whether some assignment makes $f$ true, and when one exists, find the assignment that comes first in lexicographic order.

An assignment is the sequence $x_1, x_2, \dots, x_N$ in which each $x_i$ is 0 (false) or 1 (true). To compare two assignments, read them from $x_1$ and find the first position where they differ. The one holding 0 at that position comes first.

The first line contains 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 contains one clause.

A clause is two nonzero integers $i$ and $j$ ($1 \le |i|, |j| \le N$). A positive number means the variable with that index and a negative number means the negation of that variable, so $i$ stands for $x_i$ when it is positive and for $\lnot x_{-i}$ when it is negative. The same rule applies to $j$. One clause can hold the same variable twice, and the same clause can be given more than once.

On the first line print 1 if $f$ can be made true, and 0 if it cannot.

If it can, print on the second line the assignment that comes first in lexicographic order, from $x_1$ to $x_N$, separated by spaces. Print 1 for true and 0 for false. If it cannot, print only the first line.