Description
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.
Input
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.
Output
Output a line containing "YES" or "NO".
通过2-sat性质可知连接a->b可以看为：如果选择了ai，则必须也要选择bj。这里如果a and b=1时很明显a和b都不可能等于0。所以连接 a->a1，b->b1,以保证合法时a b一定取1。a or b==0的情况类似处理。
大致建图如下
如果a and b==0。连接a1->b b1->a。
如果a and b==1。连接a1->b1 b1->a1 a->a1，b->b1
如果a or b==0。连接a1->a b1->b a1->b b1->a
如果a or b==1。连接a->b1 b->a1
如果a xor b==0。连接a->b1 a1->b b->a1 b1->a
如果a xor b==1。连接a->b a1->b1 b->a b1->a'
建图完成后直接判断2-sat即可。