分数: 500 点
问题陈述
有一个连通的简单无向图 N 顶点和 M 边,其中顶点编号 1, \dots ,N 且边缘已编号 1, \dots ,M。 边缘 i 连接顶点 A_i 和 B_i。 另外,一共有 N+1 卡片,每张卡片上的整数来自 上面写着 0 to N 。
Snuke按顺序执行了以下操作:
- 在每个顶点放置一张卡,并吃掉剩余的一张卡。
- 对于每个 i\ (1 \le i \le M),写在边缘 i 按位 \mathrm{XOR} 写在放置在顶点的两张卡片上的整数 A_i 和 B_i。令这个整数为 X_i.
- 丢弃放置在顶点上的所有卡牌。
给定有关图的信息 (N,M,A_1,\dots ,A_M,B_1,\dots ,B_M,X_1,\dots ,X_M),确定Snuke吃掉的卡片上写的整数。如果不能唯一确定,则输出 -1。
保证给定的
通过以上操作即可得到 X 。
你被给予 T 测试用例;解决它们中的每一个。
什么是按位 \mathrm{XOR}?
按位 \mathrm{XOR} 非负整数 A 和 B, A \oplus B,定义如下:
- 在二进制表示中 A \oplus B,中的数字 2^k (k \geq 0) 地方是 1 如果恰好是其中的数字之一 2^k 放置在二进制表示中 A 和 B is 1,和 0 否则。
一般来说,按位 \mathrm{XOR} of k 非负整数 p_1, p_2, p_3, \dots, p_k 定义为 (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k),并且可以证明这不取决于顺序 p_1, p_2, p_3, \dots, p_k.
约束
- 1 \le T \le 10^4
- 1 \le N \le 2 \times 10^5
- 0 \le M \le 2 \times 10^5
- 1 \le A_i,B_i \le N
- 给定的图是一个连通的简单无向图。
- X_1,\dots ,X_M 可以通过问题陈述中的运算得到。
- 总和 N 所有测试用例最多 2 \times 10^5.
- 总和 M 所有测试用例最多 2 \times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N M A_1 B_1 X_1 A_2 B_2 X_2 \vdots A_M B_M X_M
输出
输出 T 行。
的 i- 第行应该包含写在 Snuke 吃的卡上的整数 i-第一个测试用例(如果可以唯一确定),并且 -1 否则。
示例输入 1
3 2 1 1 2 3 1 0 4 4 2 1 4 1 3 5 1 4 7 2 3 1
示例输出 1
0 -1 2
对于第一个测试用例,图表如下所示。

写在放置在顶点的卡片上的可能的整数对 1 和 2 是 (1,2) 和 (2,1);无论哪种情况,Snuke 吃掉的卡片上写的整数都是 0.
对于第二个测试用例,Snuke ate 的卡上写有两个可能的整数: 0 和 1.
对于第三个测试用例,图表如下所示。
