AT_arc214_b [ARC214B] Missing Number in Graph

$ N $ 頂点の $ M $ 辺の連結な単純無向グラフがあり、頂点には $ 1, \dots ,N $ の番号、辺には $ 1, \dots ,M $ の番号がついています。 辺 $ i $ は頂点 $ A_i $ と頂点 $ B_i $ を結んでいます。 また、 $ 0 $ から $ N $ までの整数が書かれたカードがそれぞれ $ 1 $ 枚ずつ、合計 $ N+1 $ 枚あります。 すぬけ君は以下の操作を順番に行いました。 1. 各頂点に $ 1 $ 枚ずつカードを置き、残った $ 1 $ 枚のカードを食べる。 2. 各 $ i\ (1 \le i \le M) $ について、頂点 $ A_i,B_i $ に置かれた $ 2 $ 枚のカードに書かれた整数のビット単位 $ \mathrm{XOR} $ を辺 $ i $ に書く。この整数を $ X_i $ とする。 3. 頂点に置かれたカードを全て捨てる。 グラフの情報（ $ 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 $ である。 例えば、 $ 3 \oplus 5 = 6 $ となります (二進表記すると: $ 011 \oplus 101 = 110 $ )。 一般に $ 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 $ の順番によらないことが証明できます。

入力は以下の形式で標準入力から与えられる。 > $ 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` を出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースについて、グラフは下図の通りです。  頂点 $ 1,2 $ に置かれたカードに書かれた整数の組は $ (1,2) $ と $ (2,1) $ がありえますが、いずれの場合もすぬけ君が食べたカードに書かれた整数は $ 0 $ です。 $ 2 $ つ目のテストケースについて、すぬけ君が食べたカードに書かれた整数は $ 0,1 $ の $ 2 $ 通りがありえます。 $ 3 $ つ目のテストケースについて、グラフは下図の通りです。  ### 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 $ - 与えられるグラフは連結な単純無向グラフである - $ X_1,\dots ,X_M $ は問題文中の操作で得られるものである - 全てのテストケースにおける $ N $ の総和は $ 2 \times 10^5 $ 以下 - 全てのテストケースにおける $ M $ の総和は $ 2 \times 10^5 $ 以下 - 入力される値は全て整数