Distance Sum Maximization

A tree with $N$ vertices (an undirected graph with no cycles that is connected) is given. The vertices are numbered from $1$ to $N$, and the edges are numbered from $1$ to $(N-1)$.

Write a program that processes the following query.

• $u$ $v$: For a vertex $x$ ($1\le x\le N$), print the maximum value of $\operatorname{dist}(x,u)$ + $\operatorname{dist}(x,v)$. ($1\le u,v\le N$)

Here $\operatorname{dist}(x,y)$ is the number of edges on the shortest path from vertex $x$ to vertex $y$. For every vertex $x$ of the tree, $\operatorname{dist}(x,x) = 0$.

The first line contains the number of vertices $N$ ($2\le N\le 300\,000$).

Each of the next $(N-1)$ lines describes the tree. The $i$-th line contains the two vertices connected by edge $i$, separated by a space.

The next line contains the number of queries $Q$ ($2\le Q\le 300\,000$). Each of the following $Q$ lines contains one query.

Print the answers to the $Q$ queries in order, one per line.