CNF 2

2000ms

262144K

Description:

'In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of clauses, where a clause is a disjunction of literals' (cited from https://en.wikipedia.org/wiki/Conjunctive_normal_form)

In the other words, CNF is a formula of type $\text{[math]}$ , where & represents a logical "AND" (conjunction), $\text{[math]}$ represents a logical "OR" (disjunction), and v_ij are some boolean variables or their negations. Each statement in brackets is called a clause, and v_ij are called literals.

You are given a CNF containing variables x₁, ..., x_m and their negations. We know that each variable occurs in at most two clauses (with negation and without negation in total). Your task is to determine whether this CNF is satisfiable, that is, whether there are such values of variables where the CNF value is true. If CNF is satisfiable, then you also need to determine the values of the variables at which the CNF is true.

It is guaranteed that each variable occurs at most once in each clause.

Input:

The first line contains integers n and m (1 ≤ n, m ≤ 2·10⁵) — the number of clauses and the number variables, correspondingly.

Next n lines contain the descriptions of each clause. The i-th line first contains first number k_i (k_i ≥ 1) — the number of literals in the i-th clauses. Then follow space-separated literals v_ij (1 ≤ |v_ij| ≤ m). A literal that corresponds to v_ij is x_{|v_ij|} either with negation, if v_ij is negative, or without negation otherwise.

Output:

If CNF is not satisfiable, print a single line "NO" (without the quotes), otherwise print two strings: string "YES" (without the quotes), and then a string of m numbers zero or one — the values of variables in satisfying assignment in the order from x₁ to x_m.

Sample Input:

2 2
2 1 -2
2 2 -1

Sample Output:

YES
11

Sample Input:

Sample Output:

NO

Sample Input:

Sample Output:

YES
100010

Note:

In the first sample test formula is $\text{[math]}$ . One of possible answer is x₁ = TRUE, x₂ = TRUE.

Informação

Provedor Codeforces

Código CF571C