Graph of operations - Problems

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

The first line contains the number of vertices n and edges m in a graph (1 ≤ n ≤ 1000, 0 ≤ m ≤ 300000). The next m lines describe the edges. Each edge is given by the numbers of connected vertices u_i, v_i (1 ≤ u_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

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

Time limit 1 second

Memory limit 128 MiB

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

Show problem classification