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 (ui,vi) for the value of f(ui,vi). Help bobo answer them.
Input
The input consists of several tests. For each tests:
The first line contains 2 integers n,q (4≤n≤106,1≤q≤106). Each of the following (n - 1) lines contain 2 integers ai,bi denoting an edge between vertices ai and bi (1≤ai,bi≤n). Each of the following q lines contains 2 integer u′i,v′i (1≤ui,vi≤n).
The queries are encrypted in the following manner.
u1=u′1,v1=v′1.
For i≥2, ui=u′i⊕f(ui - 1,vi - 1),vi=v′i⊕f(ui-1,vi-1).
Note ⊕ denotes bitwise exclusive-or.
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 hand-written input utilities.
Output
For each tests:
For each queries, a single number denotes the value.
Sample Input
4 1
1 2
1 3
1 4
2 3
5 2
1 2
1 3
2 4
2 5
1 2
7 6
Sample Output
4
3
1