题目描述

有 $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$。

接下来 $M$行，每行包含三个整数$a,b,c$，以及一个位运算（$AND,OR,XOR$ 中的一个）。

输出格式

输出结果，如果存在，输出 YES，否则输出 NO。

样例

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

YES

数据范围

$1≤N≤1000,1≤M≤10^6$

来源

• 算法竞赛进阶指南