← 返回题目列表

Codeforces · 641/F

F. 小阿乔姆和 2-SAT

中文机器翻译题面 查看原题

小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$$。