Задан неориентированный граф. Каждому ребру (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" в противном случае.