/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
N 頂点の M 辺の連結な単純無向グラフがあり、頂点には 1, \dots ,N の番号、辺には 1, \dots ,M の番号がついています。 辺 i は頂点 A_i と頂点 B_i を結んでいます。 また、0 から N までの整数が書かれたカードがそれぞれ 1 枚ずつ、合計 N+1 枚あります。
すぬけ君は以下の操作を順番に行いました。
- 各頂点に 1 枚ずつカードを置き、残った 1 枚のカードを食べる。
- 各 i\ (1 \le i \le M) について、頂点 A_i,B_i に置かれた 2 枚のカードに書かれた整数のビット単位 \mathrm{XOR} を辺 i に書く。この整数を X_i とする。
- 頂点に置かれたカードを全て捨てる。
グラフの情報（N,M,A_1,\dots ,A_M,B_1,\dots ,B_M,X_1,\dots ,X_M）が与えられるので、すぬけ君が食べたカードに書かれた整数を特定して下さい。ただし、一意に定まらない場合は -1 を出力して下さい。
なお、与えられる X が上記の操作で得られるものであることは保証されます。
T 個のテストケースが与えられるので、それぞれについて答えを求めて下さい。
ビット単位 \mathrm{XOR} 演算とは
非負整数 A, B のビット単位 \mathrm{XOR} 、A \oplus B は、以下のように定義されます。
- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\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 行目には 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 つ目のテストケースについて、グラフは下図の通りです。
頂点 1,2 に置かれたカードに書かれた整数の組は (1,2) と (2,1) がありえますが、いずれの場合もすぬけ君が食べたカードに書かれた整数は 0 です。
2 つ目のテストケースについて、すぬけ君が食べたカードに書かれた整数は 0,1 の 2 通りがありえます。
3 つ目のテストケースについて、グラフは下図の通りです。
Score : 500 points
Problem Statement
There is a connected simple undirected graph with N vertices and M edges, where the vertices are numbered 1, \dots ,N and the edges are numbered 1, \dots ,M. Edge i connects vertices A_i and B_i. Also, there are a total of N+1 cards, one each with the integers from 0 to N written on them.
Snuke performed the following operations in order:
- Place one card on each vertex, and eat the remaining one card.
- For each i\ (1 \le i \le M), write on edge i the bitwise \mathrm{XOR} of the integers written on the two cards placed on vertices A_i and B_i. Let this integer be X_i.
- Discard all cards placed on the vertices.
Given the information about the graph (N,M,A_1,\dots ,A_M,B_1,\dots ,B_M,X_1,\dots ,X_M), determine the integer written on the card that Snuke ate. If it cannot be uniquely determined, output -1.
It is guaranteed that the given X can be obtained by the above operations.
You are given T test cases; solve each of them.
What is bitwise \mathrm{XOR}?
The bitwise \mathrm{XOR} of non-negative integers A and B, A \oplus B, is defined as follows:
- In the binary representation of A \oplus B, the digit in the 2^k (k \geq 0) place is 1 if exactly one of the digits in the 2^k place in the binary representations of A and B is 1, and 0 otherwise.
In general, the bitwise \mathrm{XOR} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k), and it can be proved that this does not depend on the order of p_1, p_2, p_3, \dots, p_k.
Constraints
- 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
- The given graph is a connected simple undirected graph.
- X_1,\dots ,X_M can be obtained by the operations in the problem statement.
- The sum of N over all test cases is at most 2 \times 10^5.
- The sum of M over all test cases is at most 2 \times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N M A_1 B_1 X_1 A_2 B_2 X_2 \vdots A_M B_M X_M
Output
Output T lines.
The i-th line should contain the integer written on the card Snuke ate for the i-th test case if it can be uniquely determined, and -1 otherwise.
Sample Input 1
3 2 1 1 2 3 1 0 4 4 2 1 4 1 3 5 1 4 7 2 3 1
Sample Output 1
0 -1 2
For the first test case, the graph is as shown below.
The possible pairs of integers written on the cards placed on vertices 1 and 2 are (1,2) and (2,1); in either case, the integer written on the card Snuke ate is 0.
For the second test case, there are two possible integers written on the card Snuke ate: 0 and 1.
For the third test case, the graph is as shown below.