У вас есть неориентированный граф из \(n\) вершин, и у каждого ребра есть вес.
Назовем простым циклом цикл в графе без повторяющихся вершин. Назовем весом цикла исключающее ИЛИ весов его ребер.
Скажем, что граф хороший, если все его простые циклы имеют вес \(1\). Граф плохой, если он является не хорошим.
Первоначально, граф пустой. Далее приходят \(q\) запросов. Каждый запрос имеет следующий вид:
- \(u\) \(v\) \(x\) — нужно добавить ребро между вершинами \(u\) и \(v\) веса \(x\), если добавление данного ребра не делает граф плохим.
Для каждого запроса выведите: было ли добавлено данное ребро.
Выходные данные
Для каждого запроса, выведите YES, если ребро было добавлено в граф, или NO в противном случае (оба в любом регистре).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9 12
6 1 0
1 3 1
3 6 0
6 2 0
6 4 1
3 4 1
2 4 0
2 5 0
4 5 0
7 8 1
8 9 1
9 7 0
|
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
NO
|