您有一个由 $$$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