题目描述

0x60图论（0x67 Tarjan算法与有向图连通性）例题4：卡图难题

有 $N$ 个变量 $X_0 ~ X_{n-1}$ ，每个变量的可能取值为 $0$ 或 $1$ 。

给定 $M$ 个算式，每个算式形如 $X_a \ op \ X_b=c$ ，其中 $a$ , $b$ 是变量编号，$c$ 是数字 $0$ 或 $1$，$op$ 是 $and$ ，$or$，$xor$ 三个位运算之一。

求是否存在对每个变量的合法赋值，使所有算式都成立。

输入格式

第一行两个整数 $N \ M$（$1 \le N \le 1000,1 \le M \le 10^6$）。

下来 $M$ 行，每行包含三个整数 $a \ b \ c$ ，以及一个位运算。

输出格式

输出一行。如果存在，输出“YES”，否则输出“NO”。

输入输出样例

输入 #1

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

输出 #1

YES