Chef and XOR Queries

All submissions for this problem are available.
Mr. X has given the Chef an undirected tree T with n nodes numbered from 1 to n. Each edge e_{i} of the tree has a nonnegative integer w_{i} written on it. But the edge weights are hidden from you. You have access only to the structure of the tree. ie. you know all the edges e_{i}.
Mr. X. has taught Chef how to compute the function f(u, v) = Bitwise XOR of all the numbers present on the edges in the unique path from u to v.
He now wants to test his disciple's understanding of this function. He tells the Chef various values of this function one by one. Since Mr. X. wants to test Chef's skills, this information could be wrong sometimes. You being good friends with the Chef have been asked to help him out to pass the test.
Total Q events occur each of which can be in one of the following forms:
 1 u v r:
Mr. X says that f(u, v) = r. For this type of event you must print: AC if the given information is consistent with all the previous information that you have accepted as AC and there is no way you can argue that this information is wrong. Accept this new information as correct.
 WA when you can prove that the given information is wrong and does not fit in with the previously AC events.
 2 u v:
Print the value of f(u, v) using only the information provided in the previously AC events.
If it is not possible to correctly determine this value based on only previously AC events print 1.
Input
 The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
 First line of each test case contains two space separated integers n and Q denoting the number of nodes and number of events respectively.
 Each of the next n  1 lines contains two space separated integers u v denoting that there is an edge between u and v in the tree.
 Description of Q events follow. Each line follows one of these two formats:
 1 u v r, denoting first type of event.
 2 u v, denoting second type of event.
Output
For each event print the answer to the event as described.
Constraints
 1 ≤ T ≤ 2000
 1 ≤ n ≤ 10^{5}
 1 ≤ Q ≤ 2 * 10^{5}
 1 ≤ u, v ≤ n
 1 ≤ sum of n over all the testcases ≤ 10^{5}
 1 ≤ sum of Q over all the testcases ≤ 2 * 10^{5}
 0 ≤ r ≤ 2 * 10^{9}
 0 ≤ w_{i}
 The graph represented by e_{i} is a tree
Example
Input 1 4 6 1 2 2 3 3 4 1 1 1 10 1 1 2 2 1 2 3 4 1 1 3 7 2 1 3 2 3 4 Output WA AC AC WA 6 1
Explanation
 Event 1: f(1, 1) cannot be 10. Since there is no edge between 1 and 1, it must be 0 ⇒ WA
 Event 2: You cannot argue that f(1, 2) cannot be 2. Therefore you accept it ⇒ AC. Thus now we know that the weight of the edge between 1 and 2 is 2.
 Event 3: You cannot argue that f(2, 3) cannot be 4. Therefore you accept it ⇒ AC. Thus now we know that the weight of the edge between 2 and 3 is 4.
 Event 4: f(1, 3) is xor of weights of edges 12 and 23 = 2 xor 4 = 6. Given information is wrong ⇒ WA
 Event 5: f(1, 3) is 6 as calculated above ⇒ 6
 Event 6: f(3, 4) cannot be answered using only the above information ⇒ 1
Author:  usaxena95 
Editorial  https://discuss.codechef.com/problems/XORQUERY 
Tags  acm17kgp, dsu, kgp17rol, medhard, tree, usaxena95, xor 
Date Added:  18112017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, 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. 