题目描述

Petya 今天要参加一门“计算复杂性”考试。老师给了他一个关于 2-CNF 布尔公式的问题：判断是否存在一种给变量赋值的方法，使得整个公式为真。

一个 2-CNF 公式由若干个子句的“与”组成；每个子句是两个不同变量或它们的否定的“或”。例如：

• $(a \lor b) \land (c \lor \lnot d)$
• $(\lnot a \lor \lnot b)$
• $(a \lor b) \land (a \lor \lnot b) \land (b \lor \lnot c)$

Petya 认为给出的公式是不可满足的。为了证明这一点，老师和 Petya 进行如下游戏。

初始时所有变量都没有被赋值。Petya 和老师轮流操作，Petya 先手。每次操作时，当前玩家选择一个尚未赋值的变量，并把它赋为 true 或 false。当所有变量都赋值后，游戏结束。

若最终得到的赋值使得整个公式为 false，则 Petya 获胜；否则老师获胜。

你的任务是编写程序扮演 Petya。若 Petya 没有必胜策略，应直接报告无解；否则需要在交互过程中按必胜策略下棋。

交互格式

交互开始时，评测器会先向你的程序输入一个 2-CNF 公式。

第一行包含两个整数 $n,m$，分别表示变量个数和子句个数。

接下来 $m$ 行，每行包含两个整数，描述一个子句中的两个文字。

• 若整数为正数 $x$，表示变量 $x$；
• 若整数为负数 $-x$，表示变量 $x$ 的否定；
• 变量编号为 $1$ 到 $n$；
• 同一个子句中的两个变量编号一定不同。

若 Petya 没有必胜策略，你的程序应输出：

-1 -1

然后立即结束。

否则游戏开始。你的程序扮演 Petya，评测器扮演老师。每次 Petya 操作时，你的程序输出一行：

x v

表示把第 $x$ 个变量赋值为 $v$，其中：

• $v=0$ 表示 false；
• $v=1$ 表示 true。

每次输出 Petya 的操作后，如果游戏尚未结束，你的程序需要从标准输入读入老师的一步操作，格式同样为：

x v

当所有变量都已被赋值后，你的程序应立即结束。

重要说明

每次输出一行后都必须刷新输出缓冲区。例如 C++ 中可使用：

cout << x << ' ' << v << endl;

或手动调用：

cout.flush();

若你的程序出现以下情况，会得到错误结果：

• Petya 存在必胜策略，但你的程序输出 -1 -1；
• Petya 没有必胜策略，但你的程序仍开始游戏；
• 输出了已经被赋值过的变量；
• 输出格式非法；
• 最终公式为真，即老师获胜；
• 没有及时刷新输出，导致交互超时。

交互示例 1

评测器首先给出公式：

3 2
1 2
-1 -2

一种可能的交互过程如下：

Petya:   3 1
Teacher: 2 0
Petya:   1 0

最终至少有一个子句为假，因此 Petya 获胜。

交互示例 2

评测器首先给出公式：

2 2
1 2
-1 -2

此时 Petya 没有必胜策略，应输出：

-1 -1