У вас есть неориентированный граф из \(n\) вершин, и у каждого ребра есть вес.
Назовем простым циклом цикл в графе без повторяющихся вершин. Назовем весом цикла исключающее ИЛИ весов его ребер.
Скажем, что граф хороший, если все его простые циклы имеют вес \(1\). Граф плохой, если он является не хорошим.
Первоначально, граф пустой. Далее приходят \(q\) запросов. Каждый запрос имеет следующий вид:
Для каждого запроса выведите: было ли добавлено данное ребро.
В первой строке заданы два целых числа \(n\) и \(q\) (\(3 \le n \le 3 \cdot 10^5\); \(1 \le q \le 5 \cdot 10^5\)) — количество вершин и запросов.
В следующих \(q\) строках заданы запросы — по одному в строке. Каждый запрос состоит из трех целых чисел \(u\), \(v\) и \(x\) (\(1 \le u, v \le n\); \(u \neq v\); \(0 \le x \le 1\)) — вершины ребра и его вес.
Гарантируется, что в запросах нет кратных ребер.
Для каждого запроса, выведите YES, если ребро было добавлено в граф, или NO в противном случае (оба в любом регистре).
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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач