题目描述

Katu Puzzle 用一个有向图 $G(V, E)$ 表示，其中每条边 $e(a, b)$ 都被标记了一个布尔运算符 $op$（$op \in \{$ AND, OR, XOR $\}$）和一个整数 $c$（$c \in \{0, 1\}$）。

如果能为每个顶点 $V_i$ 找到一个值 $X_i$（$X_i \in \{0, 1\}$），使得对于每条带标记 $op$ 和 $c$ 的边 $e(a, b)$，都满足下面的公式：

则称这个 Katu 是 可解 的。

运算规则如下：

给定一个 Katu Puzzle，请判断它是否可解。

输入格式

第一行包含两个整数 $N$（$1 \le N \le 1000$，顶点数）和 $M$（$0 \le M \le 10^6$，边数）。

接下来 $M$ 行，每行包含 $3$ 个整数 $a$（$0 \le a < N$），$b$（$0 \le b < N$），$c$ 和一个运算符 $op$，描述一条边。

输出格式

如果可解，输出 YES；否则输出 NO。

输入示例 1

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

输出示例 1

YES

示例 1 说明

取 $X_0 = 1, X_1 = 1, X_2 = 0, X_3 = 1$，可以验证：

• $X_0 \;\mathrm{AND}\; X_1 = 1 \;\mathrm{AND}\; 1 = 1$ ✓
• $X_1 \;\mathrm{OR}\; X_2 = 1 \;\mathrm{OR}\; 0 = 1$ ✓
• $X_3 \;\mathrm{AND}\; X_2 = 1 \;\mathrm{AND}\; 0 = 0$ ✓
• $X_3 \;\mathrm{XOR}\; X_0 = 1 \;\mathrm{XOR}\; 1 = 0$ ✓

所以输出 YES。

输入示例 2

2 4
0 1 1 AND
0 1 0 AND
0 1 1 OR
0 1 0 OR

输出示例 2

NO

示例 2 说明

四条约束分别要求 $X_0 \;\mathrm{AND}\; X_1$ 同时等于 $0$ 和 $1$、$X_0 \;\mathrm{OR}\; X_1$ 同时等于 $0$ 和 $1$，显然矛盾，无解。

约束条件

• $1 \le N \le 1000$
• $0 \le M \le 10^6$
• $0 \le a, b < N$
• $c \in \{0, 1\}$
• $op \in \{$ AND, OR, XOR $\}$
• 所有数值均为整数

来源

POJ Founder Monthly Contest – 2008.07.27