Count on the path

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.

The input consists of several tests. For each tests:

The first line contains 2 integers n,q (4≤n≤10⁶,1≤q≤10⁶). 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₁=u′₁,v₁=v′₁.
For i≥2, u_i=u′_i⊕f(u_{i - 1},v_{i - 1}),v_i=v′_i⊕f(u_i-1,v_i-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.

For each tests:

For each queries, a single number denotes the value.

4 1
1 2
1 3
1 4
2 3
5 2
1 2
1 3
2 4
2 5
1 2
7 6

4
3
1

Xiaoxu Guo (ftiasch)

2014 Multi-University Training Contest 5