eolymp
Competitions

2011 Зимняя Школа, Харьков, День 8, День Виталия Гольдштейна

Graph of operations

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 (1n1000, 0m300000). The next m lines describe the edges. Each edge is given by the numbers of connected vertices ui, vi (1ui, vin, uivi), the value of ci 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