eolymp
bolt
Try our new interface for solving problems
Problems

Graph of operations

Graph of operations

Time limit 1 second
Memory limit 128 MiB

The undirected graph is given. For each edge (u, v) some binary operation and the value of c are given. The number c can take the values of 0 or 1, and the operation can be one of the next: the logical multiplication (AND), the logical addition (OR) and the addition by modulo two (XOR). You need, if its possible, to assign to each vertex u the value of 0 or 1 (lets denote this value as A(u)) in a such way, that for every edge (u, v) the result of assigned to it binary operation on values A(u) and A(v) equals to the number c, written on this edge.

The rules of operations are next:

  • (0 AND 1) = (1 AND 0) = (0 AND 0) = 0, (1 AND 1) = 1

  • (0 OR 1) = (1 OR 0) = (1 OR 1) = 1, (0 OR 0) = 0

  • (0 XOR 1) = (1 XOR 0) = 1, (1 XOR 1) = (0 XOR 0) = 0

Input data

The first line contains the number of vertices n and edges m in a graph (1n1000, 0m300000). The next m lines describe the edges. Each edge is given by the numbers of connected vertices u[i], v[i] (1u[i], v[i]n, u[i]v[i]), the value of c[i] and the name of operation (AND, OR or XOR). No edge is given in a list more than one time.

Output data

Print "YES" if you can find the desired set of values for vertices, and "NO" otherwise.

Examples

Input example #1
3 3
1 2 1 OR
2 3 1 AND
1 3 1 XOR
Output example #1
YES
Input example #2
3 2
1 2 1 AND
2 3 0 OR
Output example #2
NO
Author Vitaly Goldstein
Source 2011 Winter School, Kharkov, Day 9