

Count on the pathTime Limit: 5000/2500 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 2334 Accepted Submission(s): 505 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  
