2-SAT 사전순 최소 배정

2-SAT은 불리언 변수 $x_1, x_2, \dots, x_N$의 값을 정해서 주어진 2-CNF 식을 참으로 만드는 문제다.

2-CNF 식은 $(x \lor y) \land (\lnot y \lor z) \land (x \lor \lnot z) \land (z \lor y)$ 같은 꼴이다. 괄호로 묶인 부분을 절이라고 하고, 절은 변수 두 개를 $\lor$로 이은 식이다. $\lor$는 OR, $\land$는 AND, $\lnot$은 NOT을 뜻한다.

변수의 개수 $N$과 절의 개수 $M$, 그리고 식 $f$가 주어진다. $f$를 참으로 만드는 배정이 있는지 판정하고, 있으면 그중 사전순으로 가장 앞서는 배정을 구하는 프로그램을 작성하시오.

배정은 각 $x_i$가 0(거짓) 또는 1(참)인 길이 $N$의 수열 $x_1, x_2, \dots, x_N$이다. 두 배정을 비교할 때는 $x_1$부터 차례로 값을 견주어, 값이 처음 달라지는 자리에서 0인 쪽이 앞선다.

첫째 줄에 변수의 개수 $N$ ($1 \le N \le 10000$)과 절의 개수 $M$ ($1 \le M \le 100000$)이 주어진다. 둘째 줄부터 $M$개의 줄에 절이 한 개씩 주어진다.

각 절은 0이 아닌 두 정수 $i$와 $j$ ($1 \le |i|, |j| \le N$)로 이루어진다. 양수는 그 번호의 변수를, 음수는 그 변수의 부정을 뜻한다. 즉 $i$가 양수면 $x_i$를, 음수면 $\lnot x_{-i}$를 나타내고 $j$도 같은 규칙을 따른다. 한 절에 같은 변수가 두 번 나올 수 있고, 같은 절이 여러 번 주어질 수 있다.

첫째 줄에 식 $f$를 참으로 만들 수 있으면 1을, 없으면 0을 출력한다.

만들 수 있으면 둘째 줄에 사전순으로 가장 앞서는 배정을 $x_1$부터 $x_N$까지 공백으로 구분해 출력한다. 참은 1, 거짓은 0으로 적는다. 만들 수 없으면 첫째 줄만 출력한다.