CNF 2
Contest: Codeforces Round 317 [AimFund Thanks-Round] (Div. 1)
Difficulty rating: 2500
Tags: constructive algorithms, dfs and similar, graphs, greedy

'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 $$( v _ { 1 1 } \mid v _ { 1 2 } \mid \ldots \mid v _ { 1 k _ { 1 } } ) \& ( v _ { 2 1 } \mid v _ { 2 2 } \mid \ldots \mid v _ { 2 k _ { 2 } } ) \& \ldots \& ( v _ { l 1 } \mid v _ { l 2 } \mid \ldots \mid v _ { l k _ { l } } )$$, where & represents a logical "AND" (conjunction), $$\text{The text is not rendered as an equation but as plain text.}$$ represents a logical "OR" (disjunction), and vij are some boolean variables or their negations. Each statement in brackets is called a clause, and vij are called literals.

You are given a CNF containing variables x1, ..., xm 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 format:
The first line contains integers n and m (1 ≤ n, m ≤ 2·105) — 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 ki (ki ≥ 1) — the number of literals in the i-th clauses. Then follow space-separated literals vij (1 ≤ |vij| ≤ m). A literal that corresponds to vij is x|vij| either with negation, if vij is negative, or without negation otherwise.

Output format:
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 x1 to xm.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample test formula is $$(x_{1}|\neg x_{2})\&(x_{2}|\neg x_{1})$$. One of possible answer is x1 = TRUE, x2 = TRUE.

Example input:
2 2
2 1 -2
2 2 -1

Example output:
YES
11

Example input:
4 3
1 1
1 2
3 -1 -2 3
1 -3

Example output:
NO

Editorial:
Firstly let's assign values to variables occurring in our fomula only with negation or only without negation. After that we can throw away the disjuncts which contained them, since they are already true, and continue the process until it is possible. To make it run in time limit, one should use dfs or bfs algorithm to eliminate these variables and disjuncts.
So now we have only variables which have both types of occurrences in disjucnts. Let's build a graph with the vertices corresponding to disjuncts, and for each varible a make an edge between the disjuncts that contain a and !a. Now we should choose the directions of edges in this graph in such a way that every vertex has at least one incoming edge.
We can notice that if some connected component of this graph is a tree, the solution is not possible: on each step we can take some leaf of this tree, and we have to orient its only edge to it, and then erase the leaf. In the end we'll have only one vertex, and it'll not have any incoming edges.
Otherwise, take some cycle in the component and orient the edges between neighbouring vertices along it. Then run dfs from every vertex of the cycle and orient each visited edge in the direction we went along it. It is easy to easy that after this process every vertex will have at least one incoming edge.
So, we should consider cases with the variables which values can be assigned at once, than construct a graph from disjuncts and variables and find whether each connected component has a cycle. If so, we also should carefully construct the answer, assigning the remaining variables their values, looking at the directions of the edges in the graph. The overall complexity is O(n + m).