← 返回题目列表

Codeforces · 571/C

C. 合取范式 2

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

“在布尔逻辑中,如果一个公式是子句的合取,则它是合取范式(CNF)或子句范式,其中子句是文字的析取”(引用自https://en.wikipedia.org/wiki/Conjunctive_normal_form)

换句话说,CNF 是 $$( 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 } } )$$,其中 & 表示逻辑“AND”(连词),$$\text{文本不呈现为方程式,而是呈现为纯文本。}$$ 表示逻辑“OR”(或或),vij 是一些布尔变量或其否定。括号中的每个语句称为子句,vij 称为文字。

给你一个包含变量 x1, ..., xm 及其否定的 CNF。我们知道每个变量最多出现在两个子句中(总共有否定和没有否定)。你的任务是确定这个 CNF 是否可满足,即是否存在 CNF 值为 true 的变量值。如果 CNF 可满足,那么您还需要确定 CNF 为真的变量值。

保证每个变量在每个子句中最多出现一次。

输入

第一行包含整数 n 和 m (1 ≤ n, m ≤ 2·105) — 相应的子句数和变量数。

接下来的 n 行包含每个子句的描述。第 i 行首先包含第一个数字 ki (ki ≥ 1) — 第 i 个子句中的文字数量。然后跟随空格分隔的文字 vij (1 ≤ |vij| ≤ m)。对应于 vij 的文字是 x|vij|如果 vij 为负数,则使用否定,否则不使用否定。

输出

如果 CNF 不可满足,则打印一行“NO”(不带引号),否则打印两个字符串:字符串“YES”(不带引号),然后是 m 个数字零或一的字符串——满足赋值的变量值,按从 x1 到 xm 的顺序排列。

示例

输入 #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

注意

第一个示例测试公式为 $$(x_{1}|\neg x_{2})\&(x_{2}|\neg x_{1})$$。可能的答案之一是 x1 = TRUE,x2 = TRUE。