You are given a [tree] with N vertices. 

We call a sequence of vertices [A_{1}, A_{2}, \ldots, A_{K}] *cool* if dis(A_{i}, A_{(i+1)}) = i for 1 ≤ i < K. Here, dis(u, v) denotes the length of the shortest path between vertices u and v.  
Note that, the sequence A may contain duplicate vertices as well.

You need to answer M queries of the following type:
P Q : Given integers P and Q, find the maximum possible X such that there exists a *cool* sequence of length X : [A_{1}, A_{2}, \ldots, A_{X}] where A_{1} = P and A_{X} = Q.

It is guaranteed that for each query P is not a leaf vertex (it has at least two neighbours).  
It can be proven that with this constraint, a *cool* sequence starting with P and ending with Q always exists.

------ Input Format ------ 

- The first line of each test case contains two integers N and M - the number of vertices in the tree and the number of queries.
- Then, N−1 lines follow. The i^{th} line contains two space-separated integers U_{i} and V_{i} - the vertices connected by the i^{th} edge.
- Finally, M lines follow. The i^{th} line contains two space-separated integers P_{i} and Q_{i}.

------ Output Format ------ 

Output Q separate lines. The i^{th} line should contain the answer for the i^{th} query, the maximum possible X such that there exists a *cool* sequence of length X.

------ Constraints ------ 

$3 ≤ N ≤ 2\cdot 10^{5}$
$1 ≤ M ≤ 2\cdot 10^{5}$
$1 ≤ U_{i}, V_{i} ≤ N$
$1 ≤ P_{i}, Q_{i} ≤ N$, $P_{i}$ is not a leaf.

----- Sample Input 1 ------ 
7 3
1 2
2 3
1 4
4 6
6 7
1 5
1 2
6 6
6 5

----- Sample Output 1 ------ 
3
5
3

----- explanation 1 ------ 
Query $1$: Given $P = 1$ and $Q = 2$. One possible *cool* sequence with maximum length is $[1, 5, 2]$. It is valid because $dis(1, 5) = 1$ and $dis(5, 2) = 2$. It can be shown that no *cool* sequence of length greater than $3$ exists.

Query $2$: Given $P = 6$ and $Q = 6$. One possible *cool* sequence with the maximum length is $[6, 7, 4, 3, 6]$. It is valid because $dis(6, 7) = 1$, $dis(7, 4) = 2$, $dis(4, 3) = 3$, and $dis(3, 6) = 4$. It can be shown that no *cool* sequence of length greater than $5$ exists.

Difficulty: VERY_HARD
Tags: Tree algorithms

Graph algorithms

Data structures

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
import sys
int1 = lambda x: int(x) - 1
pDB = lambda *x: print(*x, end='\n', file=sys.stderr)
p2D = lambda x: print(*x, sep='\n', end='\n\n', file=sys.stderr)

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI1(rows_number):
	return [LI1() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline().rstrip()
inf = (1 << 63) - 1
md = 10 ** 9 + 7

def solve():

	def dfs(root):
		dist = [-1] * n
		dist[root] = 0
		st = [root]
		while st:
			u = st.pop()
			for v in to[u]:
				if dist[v] != -1:
					continue
				dist[v] = dist[u] + 1
				st.append(v)
		return dist

	def far(dist):
		mx = res = 0
		for u in range(n):
			if dist[u] > mx:
				(mx, res) = (dist[u], u)
		return res
	(n, m) = LI()
	to = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = LI1()
		to[u].append(v)
		to[v].append(u)
	l = far(dfs(0))
	d1 = dfs(l)
	r = far(d1)
	d2 = dfs(r)
	for _ in range(m):
		(u, v) = LI1()
		p = d1[u] + d1[v] & 1
		d = max(d1[v], d2[v])
		while d * (d + 1) // 2 & 1 != p:
			d -= 1
		print(d + 1)
testnumber = 1
for testcase in range(testnumber):
	solve()