AT_arc214_b [ARC214B] Missing Number in Graph

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: 1. Place one card on each vertex, and eat the remaining one card. 2. 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 $ . 3. 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. For example, $ 3 \oplus 5 = 6 $ (in binary: $ 011 \oplus 101 = 110 $ ). 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 $ .

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 $ 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 Explanation 1 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.  ### 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.