Airline

An airline operates regular flights that connect $n$ different airports. Each flight links two airports directly (without stopping at any other airport) and can be used in both directions. The flights are arranged so that for any starting airport $s$ and destination airport $t$, there is exactly one sequence of flights between them that does not visit any airport more than once. The number of flights in this sequence is called the distance between $s$ and $t$.

If the airline adds a flight between airports $x$ and $y$, some pairs $(s, t)$ may get a shorter route. The more pairs affected, the more valuable the new connection is. The airline asks you to evaluate several candidate additions $(x, y)$ by this measure.

The first line contains two integers $n$ and $q$. The next $n-1$ lines each contain two integers $u_i$ and $v_i$, a direct flight between airports $u_i$ and $v_i$. The last $q$ lines each contain two integers $x_i$ and $y_i$. In the $i$-th scenario, a direct flight between $x_i$ and $y_i$ is added to the original $n-1$ flights.

Output $q$ lines. The $i$-th line contains the number of pairs $(s, t)$ with $1 \le s < t \le n$ whose distance decreases when a direct flight between $x_i$ and $y_i$ is added to the original $n-1$ flights.

• $2 \le n \le 10^6$
• $1 \le q \le 10^5$
• $1 \le u_i \le n$; $1 \le v_i \le n$; $u_i \ne v_i$
• $1 \le x_i \le n$; $1 \le y_i \le n$; $x_i \ne y_i$
• $\sum_{i=1}^{q} d_i \le 10^7$, where $d_i$ is the distance between $x_i$ and $y_i$ in the original flight network.