Graph of operations#1934
Given an undirected graph, each edge is assigned a binary operation and a value . The value can be or , and the operation may be one of the following: logical AND (AND), logical OR (OR), or logical XOR (XOR). Determine whether it is possible to assign each vertex a value of or (denoted as ) so that for every edge , the result of the assigned binary operation on and is equal to the corresponding value assigned to that edge.
The rules for the operations are as follows:
(0 \textbf{ AND } 1) = (1 \textbf{ AND } 0) = (0 \textbf{ AND } 0) = 0, (1 \textbf{ AND } 1) = 1
(0 \textbf{ OR } 1) = (1 \textbf{ OR } 0) = (1 \textbf{ OR } 1) = 1, (0 \textbf{ OR } 0) = 0
(0 \textbf{ XOR } 1) = (1 \textbf{ XOR } 0) = 1, (1 \textbf{ XOR } 1) = (0 \textbf{ XOR } 0) = 0
The first line contains the number of vertices and the number of edges in the graph (1 \le n \le 1000, 0 \le m \le 300000). The next lines describe the edges. Each edge is described by the connected vertices u_i, v_i (1 \le u_i, v_i \le n, u_i \ne v_i), value c_i, and the operation name (AND, OR, or XOR). No edge appears more than once.
Print YES if it is possible to assign the required values to the vertices. Otherwise, print NO.
Example 1
Example 2