← 返回题目列表

AtCoder · past202306_g

G. N-SAT可满足性问题

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

问题陈述

判断是否有分配的方法 0 or 1 至每个 N 变量 x_1,x_2,\ldots,x_N 这样:

  • 对于所有人 i=1,2,\ldots,M,
    • 存在一个整数 j (1 \leq j \leq k_i) 这样 x_{a_{i,j}}=b_{i,j}.

约束

  • 1 \leq N \leq 15
  • 1 \leq M \leq 100
  • 1 \leq k_i \leq N
  • 1 \leq a_{i,1} \lt a_{i,2} \lt \ldots \lt a_{i,k_i} \leq N
  • b_{i,j} \in \{0,1 \}
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

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

5 3
1
4 0
1
5 0
2
2 0
3 1

示例输出 1

Yes

例如,分配 x_1=1, x_2=0,x_3=0,x_4=0,和 x_5=0 满足条件。


示例输入 2

1 2
1
1 0
1
1 1

示例输出 2

No