CF641F.Little Artem and 2-SAT

Little Artem is a very smart programmer. He knows many different difficult algorithms. Recently he has mastered in 2-SAT one.

In computer science, 2-satisfiability (abbreviated as 2-SAT) is the special case of the problem of determining whether a conjunction (logical AND) of disjunctions (logical OR) have a solution, in which all disjunctions consist of no more than two arguments (variables). For the purpose of this problem we consider only 2-SAT formulas where each disjunction consists of exactly two arguments.

Consider the following 2-SAT problem as an example: . Note that there might be negations in 2-SAT formula (like for _x_1 and for _x_4).

Artem now tries to solve as many problems with 2-SAT as possible. He found a very interesting one, which he can not solve yet. Of course, he asks you to help him.

The problem is: given two 2-SAT formulas f and g, determine whether their sets of possible solutions are the same. Otherwise, find any variables assignment x such that f(x) ≠ g(x).

小 Artem 是一位非常聪明的程序员，掌握了许多不同且复杂的算法。最近，他掌握了 2-SAT 算法。

在计算机科学中，2-可满足性（简称 2-SAT）是判定一个合取式（逻辑与）是否可满足这一问题的特例，其中每个析取式（逻辑或）最多包含两个参数（变量）。本题中，我们仅考虑每个析取式恰好包含两个参数的 2-SAT 公式。

以下是一个 2-SAT 问题示例：。注意，2-SAT 公式中可能出现否定（例如对 $x_1$ 和 $x_4$ 的否定）。

Artem 现在正努力求解尽可能多的 2-SAT 问题。他发现了一个非常有趣的问题，但目前还无法解决。当然，他请你来帮忙。

该问题是：给定两个 2-SAT 公式 $f$ 和 $g$，判断它们的可满足赋值集合是否完全相同；否则，找出任意一个变量赋值 $\mathbf{x}$，使得 $f(\mathbf{x}) \ne g(\mathbf{x})$。

The first line of the input contains three integers n, _m_1 and _m_2 (1 ≤ n ≤ 1000, 1 ≤ _m_1, _m_2 ≤ _n_2) — the number of variables, the number of disjunctions in the first formula and the number of disjunctions in the second formula, respectively.

Next _m_1 lines contains the description of 2-SAT formula f. The description consists of exactly _m_1 pairs of integers x__i ( - n ≤ x__i ≤ n, x__i ≠ 0) each on separate line, where x__i > 0 corresponds to the variable without negation, while x__i < 0 corresponds to the variable with negation. Each pair gives a single disjunction. Next _m_2 lines contains formula g in the similar format.

输入的第一行包含三个整数 $n$、$m_1$ 和 $m_2$（$1 \leq n \leq 1000$，$1 \leq m_1, m_2 \leq n^2$），分别表示变量个数、第一个公式中析取子句的个数以及第二个公式中析取子句的个数。

接下来的 $m_1$ 行描述 2-SAT 公式 $f$。每行恰好包含一对整数 $x_i$（$-n \leq x_i \leq n$，且 $x_i \neq 0$），其中 $x_i > 0$ 表示该变量未取反，而 $x_i < 0$ 表示该变量取反。每对整数构成一个析取子句。再接下来的 $m_2$ 行以类似格式给出公式 $g$。

If both formulas share the same set of solutions, output a single word "SIMILAR" (without quotes). Otherwise output exactly n integers x__i () — any set of values x such that f(x) ≠ g(x).

如果两个公式具有相同的解集，则输出单个单词 “SIMILAR”（不带引号）。否则，输出恰好 n 个整数 x__i （）——即任意一组满足 f(x) ≠ g(x) 的 x 值。

First sample has two equal formulas, so they are similar by definition.

In second sample if we compute first function with _x_1 = 0 and _x_2 = 0 we get the result 0, because . But the second formula is 1, because .

第一个样例中有两个相同的公式，因此根据定义它们是相似的。

在第二个样例中，若将第一个函数代入 $x_1 = 0$ 和 $x_2 = 0$ 计算，结果为 $0$，因为 。但第二个公式的值为 $1$，因为 。