Network Delay in a Computer Lab

In a computer lab, there are n computers numbered from 1 to n. These computers are connected by n-1 cables such that any two computers are connected directly or indirectly, forming a tree. When a computer sends, forwards, or receives a message, the delay incurred is equal to the number of computers that are directly connected to it (i.e. its degree). The delay in transmitting through a cable is negligible.

In other words, if a computer is directly connected to d other computers, then any message passing through it will be delayed by d time units. Note that both the sender and the receiver of a message incur this delay. However, if the sender and the receiver are the same computer, its delay is only counted once.

There are m queries. Each query is given by two integers \(u_i\) and \(v_i\), where the query asks for the shortest time required for a message to travel from computer \(u_i\) to computer \(v_i\). The time is calculated as the sum of the delays (i.e. degrees) of all computers on the unique path from \(u_i\) to \(v_i\). Formally, if the path is \(u = x_0, x_1, \dots, x_k = v\), then the total delay is

[ \text{Delay} = \begin{cases} \displaystyle \sum_{j=0}^{k} d(x_j) & \text{if } u \neq v,\[10pt] \displaystyle d(u) & \text{if } u = v, \end{cases} ]

where \(d(x)\) denotes the degree of computer \(x\). Note that when \(u=v\), the delay is counted only once.

inputFormat

The first line contains two integers n and m (1 ≤ n ≤ 2×10⁵, 1 ≤ m ≤ 2×10⁵), representing the number of computers and the number of queries respectively.

Then n-1 lines follow, each containing two integers u and v indicating that there is a cable connecting computer u and computer v.

Then m lines follow, each containing two integers u_i and v_i, representing a query where the message is sent from computer u_i to computer v_i.

outputFormat

For each query, output a single integer — the minimum time required for the message to travel from u_i to v_i.

Each answer should be printed on a new line.

sample

3 1
1 2
2 3
1 3

4