题目描述

Katu Puzzle 以一个有向图 $G(V, E)$ 的形式给出，其中每条边 $e(a, b)$ 都被标记为一个布尔运算符 $\text{op}$（AND, OR, XOR 之一）以及一个整数 $c$（$0 \leq c \leq 1$）。如果可以为每个顶点 $V_i$ 找到一个值 $X_i$（$0 \leq X_i \leq 1$），使得对于每条边 $e(a, b)$ 由 $\text{op}$ 和 $c$ 标记的情况下，以下公式成立：

那么这个 Katu 是可解的。

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

输入格式

第一行包含两个整数 $N$（$1 \leq N \leq 100$）和 $M$（$0 \leq M \leq 10,000$），分别表示顶点的数量和边的数量。

接下来的 $M$ 行中，每行包含三个整数 $a$（$0 \leq a < N$），$b$（$0 \leq b < N$），$c$ 以及一个操作符 $\text{op}$，描述这条边。

输出格式

输出一行，包含 $\texttt{YES}$ 或 $\texttt{NO}$。

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

YES