P10969 Katu Puzzle

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: $$X_a \ \text{op} \ X_b = c$$ then this Katu Puzzle is solvable. Given a Katu Puzzle, your task is to determine whether it is solvable.

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 one line containing $\texttt{YES}$ or $\texttt{NO}$.

Translated by ChatGPT 5