AT_past202306_g N-SAT

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} $ .

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} $

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

### Sample Explanation 1 For example, assigning $ x_1=1, x_2=0,x_3=0,x_4=0 $ , and $ x_5=0 $ satisfies the condition. ### 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.