MOG
Spanish
|
English

Matcom Online Grader

MOG Round #13

Ended

C - Katu Puzzle

Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)

Katu Puzzle is presented as a directed graph $G(V, E)$ with each edge $e(a, b)$ labeled by a boolean operator $op$ (one of AND, OR, XOR) and an integer $c$ $(0 \le c \le 1)$. One Katu is solvable if one can find each vertex $V_i$ a value $X_i$ $(0 \le X_i \le 1)$ such that for each edge $e(a, b)$ labeled by $op$ and $c$, the following formula holds:

$X_a$ $op$ $X_b = c$

The calculating rules are:

AND 0 1
0 0 0
1 0 1
OR 0 1
0 0 1
1 1 1
XOR 0 1
0 0 1
1 1 0


Given a Katu Puzzle, your task is to determine whether it is solvable.

Input

The first line contains two integers $N$ $(1 \le N \le 1000)$ and $M$ $(0 \le M \le 10^6)$ indicating the number of vertices and edges. The following $M$ lines contain three integers $a$ $(0 \le a \lt N)$, $b$ $(0 \le b \lt N)$, $c$ and an operator $op$ each, describing the edges.

Output

Output a line containing "YES" or "NO".

Sample test(s)

Input
4 4 0 1 1 AND 1 2 1 OR 3 2 0 AND 3 0 0 XOR
Output
YES