Polo the Penguin and the Tree

All submissions for this problem are available.
Read problems statements in Russian here
Polo, the Penguin, likes the XOR operation. Please read NOTE if you are not familiar with XOR operation.
XORsum of a list of numbers is the result of XORing all of them. XORsum of (A[1] XOR A[2] XOR ... XOR A[N]) is defined as A[1] XOR (A[2] XOR (A[3] XOR ( ... XOR A[N]))).
Apart of that, Polo, the Penguin, likes trees. He has a weighted tree consisting of N vertices.
He also likes to choose some pair of vertices U and V and find XORsum of all weights on the simple path from U to V. Help him to find the maximal number he can get .
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N denoting the number of vertices in the tree. The next N1 lines contain description of edges of the tree, one edge per line in format U[i] V[i] W[i], where U[i] and V[i] are the indices of the vertices of edge and W[i] is the weight of the edge. Vertices are numbered from 1 to N, inclusive.
Output
For each test case, output a single line containing the answer to the corresponding test case.
Constraints
 1 ≤ T ≤ 7
 1 ≤ N ≤ 100,000
 0 ≤ W[i] ≤ 1,000,000,000
Example
Input: 2 3 1 2 3 3 1 2 4 1 2 2 1 3 2 4 3 1 Output: 3 3
Explanation
Example case 1. In this case there are tree ways to choose pair of vertices:
 (1, 2): The only edge you path is edge (1, 2) with weight 3. The XORsum is simply 3.
 (1, 3): The only edge you path is edge (1, 3) with weight 2. The XORsum is simply 2.
 (2, 3): There are two edges on the path in this case: (2, 1) and (1, 3) with weights 3 and 2, respectively. The XORsum is 3 XOR 2 = 1.
So the maximal value Polo can get is 3.
Example case 2. If Polo chooses vertices 1 and 4, then the XORsum is equal to 2 XOR 1 = 3. This is the maximal value he can get in this case.
NOTE
XOR operation is a bitwise "Exclusive OR" operation performed on two integers in binary representation. First, the shorter number is prepended with leading zeroes until the numbers have equal size in binary. Then the resulting number (also in binary) contains 0 in all positions where the corresponding bits coincide, and 1 on the rest of the positions.
For example, 3 XOR 5 = 011_{2} XOR 101_{2} = 110_{2} = 6.
Author:  witua 
Tester:  rustinpiece 
Editorial  http://discuss.codechef.com/problems/PPTREE 
Tags  bitwise, cook39, dynamicprogramming, mediumhard, trie, witua, xor 
Date Added:  9102013 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 