Xortest Path

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef was practicing with some graph theory problems in CodeChef. He was trying to solve a problem involving finding the shortest path in a weighted, undirected graph. He thought it was quite standard, so he coded the solution and submitted it. Unfortunately it was judged “Wrong Answer”.
Wanting to debug, Chef downloaded Peter Xor's accepted solution. He also made a test case, illustrated by the following image:
Now, what is the cost of the shortest path from 1 to 5? Chef thought that the answer should be 36 + 16 + 18 = 70, because the other candidate path has a higher total cost of 36 + 50 + 11 + 18 = 115. But he was surprised when Peter Xor's accepted solution outputted 15! Chef was confused because he can't see any path with a total cost of 15.
After rereading the problem, Chef found his mistake. The problem's title was actually Xortest path, not Shortest path, so the problem was actually asking for the path between two given nodes with the least possible XOR! So in the example above, the answer is indeed 15, because the path 1 → 2 → 3 → 4 → 5 has an XOR cost of 36 ⊕ 50 ⊕ 11 ⊕ 18 = 15, and no other path has a lower XOR cost than this. In other words, this is the “xortest path”.
Now that Chef knows his mistake, he still has a problem; he doesn't know how to answer this problem! Your task as his souschef is to answer this problem for him. Specifically, you have to answer Q queries, where each query is a pair of nodes, and the answer is the weight of the “xortest path” between them.
Note that in this problem, a path may pass through an edge or node any number of times. (Some authors would call such a path a walk.) For instance, in the example above, the path 1 → 2 → 4 → 3 → 2 → 4 → 5 is also a “xortest path”, because its XOR cost is 36 ⊕ 16 ⊕ 11 ⊕ 50 ⊕ 16 ⊕ 18 = 15.
Input
The first line of input contains three integers, N, E and Q. Nodes are labelled 1 to N.
The following E lines describe the edges. The i^{th} line contains three integers a_{i}, b_{i} and c_{i}, which means that there is an undirected edge between nodes a_{i} and b_{i} with weight c_{i}.
The following Q lines describe the queries. The j^{th} line contains two integers x_{j} and y_{j}, which means that you need to find the “xortest path” between nodes x_{j} and y_{j}.
Output
Output Q lines, one for each query. The j^{th} line must contain a single integer, the weight of the xortest path between x_{j} and y_{j}. If there does not exist a path between these nodes, output “XIT” (without quotes) instead.
Constraints
 1 ≤ N, E, Q ≤ 10^{5}
 1 ≤ a_{i}, b_{i}, x_{j}, y_{j} ≤ N
 0 ≤ c_{i} ≤ 10^{9}
 Parallel edges or selfloops may appear.
Example
Input: 7 7 5 1 2 36 2 4 16 4 5 18 2 3 50 3 4 11 6 6 100 7 6 100 1 5 5 1 1 2 6 7 1 7 Output: 15 15 13 0 XIT
Explanation
The sample input is illustrated by the image above.
Author:  kevinsogo 
Tags  kevinsogo 
Date Added:  7062016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, 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, SCM chicken, 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. 