G - N-SAT Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

N 個の変数 x_1,x_2,\ldots,x_N にそれぞれ 0 または 1 を割り当てる方法であって、次の条件を満たすものが存在するかどうかを判定してください。

  • i=1,2,\ldots,M すべてに対し、次の条件を満たす。
    • x_{a_{i,j}}=b_{i,j} を満たす整数 j (1 \leq j \leq k_i) が存在する。

制約

  • 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

Problem Statement

Determine if there is a way to assign 0 or 1 to each of N variables x_1,x_2,\ldots,x_N so that:

  • for all i=1,2,\ldots,M,
    • there exists an integer j (1 \leq j \leq k_i) such that x_{a_{i,j}}=b_{i,j}.

Constraints

  • 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 \}
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

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}

Output

Print Yes if there is a way to assign values, and No otherwise.

Sample Input 1

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

Sample Output 1

Yes

For example, assigning x_1=1, x_2=0,x_3=0,x_4=0, and x_5=0 satisfies the condition.

Sample Input 2

1 2
1
1 0
1
1 1

Sample Output 2

No