AT_past202306_g N-SAT

判断是否存在一种方法，为每个 $N$ 个变量 $x_1,x_2,\ldots,x_N$ 分别赋值 $0$ 或 $1$，使得： - 对所有 $i=1,2,\ldots,M$，都满足： - 对于每一个 $i$，存在一个整数 $j$，$1 \leq j \leq k_i$，使得 $x_{a_{i,j}}=b_{i,j}$。

输入按如下格式从标准输入给出： > $N \ M$ > $k_1$ > $a_{1,1}\ b_{1,1}$ > $\vdots$ > $a_{1,k_1}\ b_{1,k_1}$ > $\vdots$ > $k_M$ > $a_{M,1}\ b_{M,1}$ > $\vdots$ > $a_{M,k_M}\ b_{M,k_M}$

如果存在一种赋值方案，输出 `Yes`，否则输出 `No`。

### 样例解释 1 例如，将 $x_1=1, x_2=0, x_3=0, x_4=0, x_5=0$ 时，可以满足题目要求。 ### 数据范围 - $1 \leq N \leq 15$ - $1 \leq M \leq 100$ - $1 \leq k_i \leq N$ - $1 \leq a_{i,1} < a_{i,2} < \ldots < a_{i,k_i} \leq N$ - $b_{i,j} \in \{0,1\}$ - 输入中的所有数均为整数。 由 ChatGPT 5 翻译