← 返回题目列表

AtCoder · arc214_b

B. 图表中缺少数字

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

分数: 500 点

问题陈述

有一个连通的简单无向图 N 顶点和 M 边,其中顶点编号 1, \dots ,N 且边缘已编号 1, \dots ,M。 边缘 i 连接顶点 A_i 和 B_i。 另外,一共有 N+1 卡片,每张卡片上的整数来自 上面写着 0 to N 。

Snuke按顺序执行了以下操作:

  1. 在每个顶点放置一张卡,并吃掉剩余的一张卡。
  2. 对于每个 i\ (1 \le i \le M),写在边缘 i 按位 \mathrm{XOR} 写在放置在顶点的两张卡片上的整数 A_i 和 B_i。令这个整数为 X_i.
  3. 丢弃放置在顶点上的所有卡牌。

给定有关图的信息 (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 否则。
例如, 3 \oplus 5 = 6 (二进制: 011 \oplus 101 = 110).
一般来说,按位 \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.

对于第三个测试用例,图表如下所示。