问题 A: Katu Puzzle
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
Katu Puzzle is presented as a directed graph G(V, E) with each edge e(a, b) labeled by a boolean operator op (one of AND, OR, XOR) and an integer c(0≤c≤1). One Katu is solvable if one can find each vertex Vi a value Xi(0≤Xi≤1) such that for each edge e(a, b) labeled by op and c, the following formula holds:
Xa op Xb=c
The calculating rules are:
Given a Katu Puzzle, your task is to determine whether it is solvable.
Xa op Xb=c
The calculating rules are:
|
|
|
输入
The first line contains two integers N(1≤N≤1000) and M(0≤M≤1,000,000) indicating the number of vertices and edges.
The following M lines contain three integers a(0≤a<N), b(0≤b<N), c and an operator op each, describing the edges.
The following M lines contain three integers a(0≤a<N), b(0≤b<N), c and an operator op each, describing the edges.
输出
Output a line containing "YES" or "NO".
样例输入 复制
4 4
0 1 1 AND
1 2 1 OR
3 2 0 AND
3 0 0 XOR样例输出 复制
YES提示
X0=1,X1=1,X2=0,X3=1.