题目描述

描述

Katu Puzzle 是一个有向图 $G(V, E)$，其中每条边 $e(a, b)$ 都标有一个布尔运算符 $op$（$AND$、$OR$ 或 $XOR$）和一个整数 $c$（$0 \leq c \leq 1$）。如果能够为每个顶点 $V_i$ 分配一个值 $X_i$（$0 \leq X_i \leq 1$），使得对于每条标有运算符 $op$ 和值 $c$ 的边 $e(a, b)$，满足以下等式：

那么这个 Katu Puzzle 就是可解的。布尔运算的规则如下：

• $AND$：

  $$0 \ AND \ 0 = 0$$ $$0 \ AND \ 1 = 0$$ $$1 \ AND \ 0 = 0$$ $$1 \ AND \ 1 = 1$$

• $OR$：

  $$0 \ OR \ 0 = 0$$ $$0 \ OR \ 1 = 1$$ $$1 \ OR \ 0 = 1$$ $$1 \ OR \ 1 = 1$$

• $XOR$：

  $$0 \ XOR \ 0 = 0$$ $$0 \ XOR \ 1 = 1$$ $$1 \ XOR \ 0 = 1$$ $$1 \ XOR \ 1 = 0$$

给定一个 Katu Puzzle，你的任务是判断它是否可解。

输入

第一行包含两个整数 $N$（$1 \leq N \leq 1000$）和 $M$（$0 \leq M \leq 1,000,000$），分别表示顶点数和边数。
接下来的 $M$ 行，每行包含三个整数 $a$（$0 \leq a < N$）、$b$（$0 \leq b < N$）、$c$ 和一个运算符 $op$，描述每条边。

输出

输出一行，包含 "$YES$" 或 "$NO$"。

示例输入

4 4  
0 1 1 AND  
1 2 1 OR  
3 2 0 AND  
3 0 0 XOR  

示例输出

YES  

提示

一种可行的解是：
$X_0 = 1$, $X_1 = 1$, $X_2 = 0$, $X_3 = 1$。

来源

POJ Founder Monthly Contest – 2008.07.27, Dagger