Problem Description

A Katu Puzzle is given in the form of a directed graph $G(V, E)$. Each edge $e(a, b)$ is labeled with a Boolean operator $\text{op}$ (one of AND, OR, XOR) and an integer $c$ ($0 \leq c \leq 1$). If we can find a value $X_i$ ($0 \leq X_i \leq 1$) for every vertex $V_i$ such that for every edge $e(a, b)$ labeled with $\text{op}$ and $c$, the following formula holds:

then this Katu Puzzle is solvable.

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

Input Format

The first line contains two integers $N$ ($1 \leq N \leq 100$) and $M$ ($0 \leq M \leq 10,000$), representing the number of vertices and the number of edges, respectively.

In the next $M$ lines, each line contains three integers $a$ ($0 \leq a < N$), $b$ ($0 \leq b < N$), $c$, and an operator $\text{op}$, describing the edge.

Output Format

Output one line containing $\texttt{YES}$ or $\texttt{NO}$.

4 4
0 1 1 AND
1 2 1 OR
3 2 0 AND
3 0 0 XOR

YES

Hint

Translated by ChatGPT 5