AT_arc214_b.[ARC214B] Missing Number in Graph

有一个连通的简单无向图，包含 $N$ 个顶点和 $M$ 条边，顶点编号为 $1, \dots ,N$，边编号为 $1, \dots ,M$。第 $i$ 条边连接顶点 $A_i$ 和 $B_i$。此外，还有 $N+1$ 张卡片，分别写有 $0$ 到 $N$ 的整数。

Snuke 按如下顺序进行了操作：

1. 将每个顶点放上一张卡片，剩下的一张卡片被他吃掉。
2. 对于每一条边 $i\ (1 \le i \le M)$，在第 $i$ 条边上写下放在顶点 $A_i$ 和 $B_i$ 上的卡片上数字的按位异或（bitwise XOR）结果。记该数为 $X_i$。
3. 丢弃所有放在顶点上的卡片。

现在给定关于图的信息（$N,M,A_1,\dots ,A_M,B_1,\dots ,B_M,X_1,\dots ,X_M$），请确定 Snuke 吃掉的卡片上的整数。如果不能唯一确定，输出 -1。保证所给的 $X$ 能通过题目中的操作得到。

给定 $T$ 组测试数据，请求解每组数据。

什么是按位异或（bitwise XOR）？非负整数 $A$ 和 $B$ 的按位异或 $A \oplus B$ 定义如下：

• $A \oplus B$ 的二进制表示中，第 $2^k$ 位（$k \geq 0$）如果 $A$ 和 $B$ 的二进制表示中同一位正好有一个为 $1$，则为 $1$，否则为 $0$。

例如，$3 \oplus 5 = 6$（二进制：$011 \oplus 101 = 110$）。
一般情况下，$k$ 个非负整数 $p_1,p_2,p_3,\dots,p_k$ 的按位异或定义为 $(\dots((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$，且可以证明，这与运算的顺序无关。

输入由标准输入给出，格式如下：

$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$ 行输出第 $i$ 组测试数据 Snuke 吃掉的卡片上的整数；如果无法唯一确定，则输出 -1。

样例解释 1

对于第一组测试数据，图如下所示。

顶点 $1$ 和 $2$ 上可能的卡片数字对有 $(1,2)$ 和 $(2,1)$，无论哪种，Snuke 吃掉的卡片上的数字都是 $0$。

对于第二组测试数据，Snuke 吃掉卡片的数字可能是 $0$ 或 $1$，都成立。

对于第三组测试数据，图如下所示。

数据范围

• $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$。
• 所有输入值均为整数。

由 ChatGPT 5 翻译