Problem Description

On this day, Xiaoming is studying in the computer lab.

He finds that there are a total of $n$ computers in the lab, numbered from $1$ to $n$. There are network cables connecting the computers. In total, there are $n-1$ cables connecting the $n$ computers, so that any two computers are connected either directly or indirectly.

Xiaoming notices that the time a computer needs to forward, send, or receive information depends on how many other computers it is directly connected to, while the transmission time on the cables can be ignored. For example, if a computer is directly connected to $d$ other computers by cables, then any information passing through this computer will be delayed by $d$ units of time (the sender and the receiver also produce such a delay; of course, if the sender and the receiver are the same computer, the delay is counted only once).

Xiaoming has a total of $m$ questions: if computer $u_{i}$ sends information to computer $v_{i}$, what is the minimum time for the information to travel from $u_{i}$ to $v_{i}$?

Input Format

The input has $n+m$ lines in total. The first line contains two positive integers $n, m$.

The next $n-1$ lines each contain two positive integers $x, y$, indicating that the two computers numbered $x$ and $y$ are directly connected by a cable.

The next $m$ lines each contain two positive integers $u_{i}, v_{i}$, indicating Xiaoming's $i$-th question.

Output Format

Output $m$ lines in total. The $i$-th line contains one positive integer, the answer to Xiaoming's $i$-th question.

4 3
1 2
1 3
2 4
2 3
3 4
3 3

5
6
1

Hint

Sample Explanation

The delays of these four computers are $2,2,1,1$, respectively.

For the first query, going from $2$ to $3$ needs to pass through $2,1,3$, so the total time is $2+2+1=5$. For the second query, going from $3$ to $4$ needs to pass through $3,1,2,4$, so the total time is $1+2+2+1=6$.

For the third query, going from $3$ to $3$ produces only one delay, so the time is $1$.

Constraints and Notes

For $30\%$ of the testdata, $n, m \leq 1000$.

For $100\%$ of the testdata, $n, m \leq 10^5$.

Lanqiao Cup 2022 National Contest B Group, Problem H.

Translated by ChatGPT 5