P30127

Katu Puzzle

难度 7 级 2-sat问题 强连通分量 图论
讨论 统计 1通过 1提交 100%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

有 N 个变量 $X0 \sim 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。

样例

样例 1
输入
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
Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交