

Count on the pathTime Limit: 5000/2500 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 2391 Accepted Submission(s): 507 Problem Description bobo has a tree, whose vertices are conveniently labeled by 1,2,¡,n. Let f(a,b) be the minimum of vertices not on the path between vertices a and b. There are q queries (u_{i},v_{i}) for the value of f(u_{i},v_{i}). Help bobo answer them. Input The input consists of several tests. For each tests: The first line contains 2 integers n,q (4¡Ün¡Ü10^{6},1¡Üq¡Ü10^{6}). Each of the following (n  1) lines contain 2 integers a_{i},b_{i} denoting an edge between vertices a_{i} and b_{i} (1¡Üa_{i},b_{i}¡Ün). Each of the following q lines contains 2 integer u¡ä_{i},v¡ä_{i} (1¡Üu_{i},v_{i}¡Ün). The queries are encrypted in the following manner. u_{1}=u¡ä_{1},v_{1}=v¡ä_{1}. For i¡Ý2, u_{i}=u¡ä_{i}¨’f(u_{i  1},v_{i  1}),v_{i}=v¡ä_{i}¨’f(u_{i1},v_{i1}). Note ¨’ denotes bitwise exclusiveor. It is guaranteed that f(a,b) is defined for all a,b. The task contains huge inputs. `scanf` in g++ is considered too slow to get accepted. You may (1) submit the solution in c++; or (2) use handwritten input utilities. Output For each tests: For each queries, a single number denotes the value. Sample Input
Sample Output
Author Xiaoxu Guo (ftiasch) Source  
