19837번 - Game of 2-SAT 다국어인터랙티브

Today Petya has an exam on Computational Complexity. He has the following task.

There is a boolean formula in 2-CNF. The task is to determine whether it is possible to assign values true or false to its variables so that the formula evaluates to true.

A boolean formula has several variables. Each of them can be equal to either true or false. A formula in 2-CNF is defined as follows:

• It is a conjunction (i.e. <<and>> operation) of one or more disjuncts.
• Each disjunct is an <<or>> operation applied to two distinct variables or their negations.
• Each variable can be in several disjuncts.
• Some variables may not appear in any disjuncts.

There are a few examples of boolean formulas in 2-CNF (symbols <<$\&$>>, <<$|$>>, <<$!$>> mean <<and>>, <<or>>, <<not>> respectively):

• $(a | b) \& (c | !d)$
• $(!a | !b)$
• $(a | b) \& (a | !b) \& (b | !c)$

Petya thinks that the answer is <<impossible>>. Now he has to prove it to the teacher. To do this the teacher has proposed him an interesting game.

In the beginning of the game the variables are not assigned any values. Petya and the teacher take alternating turns, starting with Petya. Each turn the current player assigns true or false to any unassigned variable. The game ends when there are no unassigned variables left.

If the formula equates to false for the final assignment of variables, Petya wins the game and therefore passes the exam. Otherwise, Petya was obviously wrong, and he fails the exam.

Your task is to help Petya pass his exam. Write a program to play the game against the teacher. If Petya has no winning strategy, you should inform them not to spend time for a hopeless game.

In the beginning of the input, a formula in 2-CNF is given. The first line contains two integers $n$ and $m$ --- number of variables and the number of disjuncts ($2 \le n \le 10^4$, $1 \le m \le 2 \cdot 10^4$).

Then disjuncts follow in $m$ lines. Each of them is defined by two integers --- indices of variables. If a variable appears in the disjunct with a negation then its index is given with a minus sign. Variables are numbered from $1$ to $n$.

If Petya has no winning strategy, you should output "-1 -1" and terminate.

Otherwise, the game starts. Your program plays as Petya and jury's program plays as the teacher. Each turn the current player prints two integers in a single line. An assignment of value $v$ to the $x$-th variable is denoted by a line "x v". Here $v=0$ means false and $v=1$ means true.

Your program should print each Petya's turn to stdout. After each turn, if the game is not over yet, your program should read teacher's turn from stdin.

When the game ends, your program should terminate.