CNF 2

题意翻译

### 题目描述 你有 $m$ 个变量 $b_k$。令 $c_i=a_{i,1}|\dots|a_{i,k_i}(1\le i\le n)$，你希望使 $f=c_1\&\dots\&c_n$ 为真，其中 $a_{i,j}$ 是 $b_k$ 或 $\neg b_k$。 每个 $c_i$ 中最多只含一个 $b_k$，$f$ 最多只含两个 $b_k$。问是否存在方案使 $f$ 为真。 ### 输入格式 第一行两个正整数 $n,m$。 接下来 $n$ 行，每行第一个正整数 $k_i$，接下来 $k_i$ 个整数 $a_{i,j}$。 ### 输出格式 若不存在方案，第一行输出`NO`，否则第一行输出`YES`，第二行输出 $m$ 个数，为 $b_k$ 的取值。

题目描述

'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 , where $ & $ represents a logical "AND" (conjunction),  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_{1},...,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.

输入输出格式

输入格式

The first line contains integers $ n $ and $ m $ ( $ 1<=n,m<=2·10^{5} $ ) — 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_{|vij}| $ either with negation, if $ v_{ij} $ is negative, or without negation otherwise.

输出格式

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_{1} $ to $ x_{m} $ .

输入输出样例

输入样例 #1

2 2
2 1 -2
2 2 -1

输出样例 #1

YES
11

输入样例 #2

4 3
1 1
1 2
3 -1 -2 3
1 -3

输出样例 #2

NO

输入样例 #3

5 6
2 1 2
3 1 -2 3
4 -3 5 4 6
2 -6 -4
1 5

输出样例 #3

YES
100010

说明

In the first sample test formula is . One of possible answer is $ x_{1}=TRUE,x_{2}=TRUE $ .

题意翻译

### 题目描述 你有 $m$ 个变量 $b_k$。令 $c_i=a_{i,1}|\dots|a_{i,k_i}(1\le i\le n)$，你希望使 $f=c_1\&\dots\&c_n$ 为真，其中 $a_{i,j}$ 是 $b_k$ 或 $\neg b_k$。 每个 $c_i$ 中最多只含一个 $b_k$，$f$ 最多只含两个 $b_k$。问是否存在方案使 $f$ 为真。 ### 输入格式 第一行两个正整数 $n,m$。 接下来 $n$ 行，每行第一个正整数 $k_i$，接下来 $k_i$ 个整数 $a_{i,j}$。 ### 输出格式 若不存在方案，第一行输出`NO`，否则第一行输出`YES`，第二行输出 $m$ 个数，为 $b_k$ 的取值。