Katu Puzzle

Given a directed graph G(V, E) where each edge e(a, b) is labeled with a Boolean operator op (one of AND, OR, or XOR) and an integer c (with 0 \(\leq\) c \(\leq\) 1). You are required to assign each vertex V_i a value X_i (where 0 \(\leq\) X_i \(\leq\) 1) such that for every edge e(a, b) the following equation holds:

$$ X_a \; \text{op} \; X_b = c $$

If such an assignment exists, the puzzle is considered solvable.

inputFormat

The first line contains two integers n and m — the number of vertices and the number of edges respectively. Each of the following m lines contains an edge description with four entries: two integers a and b (denoting an edge from vertex a to vertex b where vertices are 1-indexed), a string op (which is either AND, OR, or XOR), and an integer c (either 0 or 1).

outputFormat

Output YES if the puzzle is solvable (i.e. there exists a valid assignment for all vertices); otherwise, output NO.

sample

2 1
1 2 AND 1

YES