30127 - Katu Puzzle

N 个变量 $X0 \sim X{N-1},每个变量的可能取值为 01$。

给定 M 个算式,每个算式形如 X_a \ op \ X_b = c,其中 a, b 是变量编号,c 是数字 01opANDORXOR 三个位运算之一。

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

输入

第一行包含两个整数 NM

接下来 M 行,每行包含三个整数 a, b, c,以及一个位运算(ANDORXOR 中的一个)。

输出

输出结果,如果存在,输出 YES,否则输出 NO

样例

输入

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

输出

YES

提示

  • 1 \le N \le 1000
  • 1 \le M \le 10^6
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题