问题陈述
判断是否有分配的方法 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