2-Sat

$N$개의 변수와 $M$개의 절로 이루어진 2-Sat가 주어진다. 충족 가능성을 확인하고, 충족 가능하다면 변수의 할당을 구성한다.

제약 조건

• $1 \leq N \leq 500,000$
• $1 \leq M \leq 500,000$

2-Sat는 DIMACS 형식으로 주어진다. 예제를 참고한다.

p cnf $N$ $M$
$a_1$ $b_1$ 0
$a_2$ $b_2$ 0
:
$a_M$ $b_M$ 0

입력이 충족 가능하면 다음과 같이 출력한다:

s SATISFIABLE
v $x_1$ $x_2$ ... $x_N$ 0

$i$-번째 변수가 참이면 $x_i = i$이고, 거짓이면 $x_i = -i$이다.

입력이 충족 가능하지 않으면 다음과 같이 출력한다:

s UNSATISFIABLE