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 翻译