“在布尔逻辑中,如果一个公式是子句的合取,则它是合取范式(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。