CF571C CNF 2

“在布尔逻辑中，如果一个公式是子句的合取，则其处于合取范式（CNF）或子句范式中，其中子句是文字的析取”（引自 https://en.wikipedia.org/wiki/Conjunctive_normal_form）。 换句话说，CNF 是形如  的公式，其中 $\&$ 表示逻辑“与”（合取），$|$ 表示逻辑“或”（析取），$v_{ij}$ 是某些布尔变量或其否定。括号中的每个语句称为一个子句，$v_{ij}$ 称为文字。 给定一个包含变量 $x_{1}, \ldots, x_{m}$ 及其否定的 CNF。已知每个变量在最多两个子句中出现（包括被否定和未被否定的情况）。你的任务是判断该 CNF 是否可满足，即是否存在一组变量赋值使得 CNF 的值为真。如果 CNF 可满足，则还需确定使 CNF 为真的变量赋值。 保证每个变量在每个子句中至多出现一次。

第一行包含整数 $n$ 和 $m$（$1 \le n, m \le 2 \times 10^{5}$）—— 分别表示子句的数量和变量的数量。 接下来的 $n$ 行描述每个子句。第 $i$ 行首先包含一个数字 $k_{i}$（$k_{i} \ge 1$）—— 第 $i$ 个子句中文字的数量。随后是空格分隔的文字 $v_{ij}$（$1 \le |v_{ij}| \le m$）。对应的文字为 $x_{|v_{ij}|}$，若 $v_{ij}$ 为负数则表示其否定，否则表示原变量。

如果 CNF 不可满足，输出一行“NO”（不带引号）。否则输出两行：第一行“YES”（不带引号），第二行一个由 $m$ 个 0 或 1 组成的字符串——按顺序从 $x_{1}$ 到 $x_{m}$ 的变量赋值。

在第一个样例中，公式为 $(x_1 | \neg x_2) \& (x_2 | \neg x_1)$。一种可能的答案为 $x_{1} = \text{TRUE}$，$x_{2} = \text{TRUE}$。 翻译由 DeepSeek R1 完成