小Artem是一个非常聪明的程序员。他知道许多不同的困难算法。最近他已经掌握了2-SAT 1。
在计算机科学中,2-可满足性(缩写为 2-SAT)是确定析取(逻辑 OR)的合取(逻辑 AND)是否有解的问题的特例,其中所有析取由不超过两个参数(变量)组成。出于解决此问题的目的,我们仅考虑 2-SAT 公式,其中每个析取恰好由两个参数组成。
以以下 2-SAT 问题为例:$$(!x_{1} \text{ OR } x_{2}) \text{ AND } (x_{3} \text{ OR }!x_{4}) \text{ AND }... \text{ AND } (x_{2n-1} \text{ OR } x_{2n})$$。请注意,2-SAT 公式中可能存在否定(例如 x1 和 x4)。
Artem 现在尝试用 2-SAT 解决尽可能多的问题。他发现了一个非常有趣的问题,但他还无法解决。当然,他请求你帮助他。
问题是:给定两个2-SAT公式f和g,判断它们的可能解集是否相同。否则,找到任何变量赋值 x 使得 f(x) ≠ g(x)。
输入
输入的第一行包含三个整数 n、m1 和 m2 (1 ≤ n ≤ 1000, 1 ≤ m1, m2 ≤ n2) - 分别是变量数、第一个公式中的析取数和第二个公式中的析取数。
接下来的 m1 行包含 2-SAT 公式 f 的描述。该描述恰好由 m1 对整数 xi ( - n ≤ xi ≤ n, xi ≠ 0) 组成,每对都在单独的行上,其中 xi > 0 对应于不带负数的变量,而 xi < 0 对应于带负数的变量。每对给出一个分离。接下来的 m2 行包含类似格式的公式 g。
输出
如果两个公式共享同一组解,则输出一个单词“SIMILAR”(不带引号)。否则准确输出 n 个整数 xi ($$x_i \in \{0, 1\}$$) - 任何值 x 的集合,使得 f(x) ≠ g(x)。
示例
输入 #1
2 1 1 1 2 1 2
输出 #1
SIMILAR
输入 #2
2 1 1 1 2 1 -2
输出 #2
0 0
注意
第一个示例有两个相等的公式,因此它们的定义相似。
在第二个示例中,如果我们使用 x1 = 0 和 x2 = 0 计算第一个函数,我们将得到结果 0,因为 $$( 0 \; \textcircled { OR } \; 0 ) = 0$$。但第二个公式是 1,因为 $$( 0 \; { \mathrm { O R } } \;! 0 ) = ( 0 \; { \mathrm { O R } } \; 1 ) = 1$$。