Графік операцій
У вас є неорієнтований граф. Кожному ребру (u, v) цього графа відповідає певна бінарна операція та число c. Число c може бути або 0, або 1, а операції можуть бути такими: логічне множення (AND), логічне додавання (OR) і додавання за модулем два (XOR). Ваше завдання — визначити, чи можна призначити кожній вершині u число 0 або 1 (позначимо це значення як A(u)) так, щоб для кожного ребра (u, v) результат відповідної бінарної операції над значеннями A(u) і A(v) дорівнював числу c, вказаному на цьому ребрі.
Правила обчислення для зазначених операцій:
(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
Вхідні дані
Перший рядок містить кількість вершин n і кількість ребер m у графі (1 ≤ n ≤ 1000, 0 ≤ m ≤ 300000). Кожен з наступних m рядків описує ребро. Ребро визначається номерами вершин u[i], v[i] (1 ≤ u[i], v[i] ≤ n, u[i] ≠ v[i]), числом c[i] і назвою операції (AND, OR або XOR). Жодне ребро не повторюється.
Вихідні дані
Виведіть "YES", якщо можна знайти такий набір значень для вершин, і "NO" в іншому випадку.