← 返回题目列表

Codeforces · 1555/F

F. 好图

中文机器翻译题面 查看原题

您有一个由 $$$n$$$ 个顶点和加权边组成的无向图。

简单循环是没有重复顶点的图的循环。令环的权重为其所包含的边的权重的异或。

假设该图是好的,如果它的所有简单循环都具有权重 $$$1$$$。如果图表不好,那么它就是坏图表。

最初,图表是空的。然后是 $$$q$$$ 查询。每个查询都有下一个类型:

- $$$u$$$ $$$v$$$ $$$x$$$ - 在权重 $$$x$$$ 的顶点 $$$u$$$ 和 $$$v$$$ 之间添加边(如果它不会使图形变得糟糕)。

对于每个查询打印,是否添加了边缘。

输入

第一行包含两个整数 $$$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(均不区分大小写)。

示例

输入 #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

输出 #1

YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
NO