Unter

Justas plans to build an app that lets people share car rides. First, he needs to write a program that finds the shortest distance between two houses.

In the city where the app will run there are $N$ houses, numbered from $1$ to $N$. The houses are directly connected by $N$ bidirectional streets. Each street connects exactly two houses, and any two houses are connected by at most one street.

Justas has already written an algorithm that finds the shortest path between two houses when there is only one way to get from one house to another without passing through the same house more than once. But he needs your help for pairs of houses for which more than one such way exists.

Find the shortest distance for $Q$ pairs of houses.

The first line contains two integers: the number of houses $N$ and the number of queries $Q$.

Each of the next $N$ lines contains two space-separated integers $a_i$ and $b_i$, meaning there is a street between houses $a_i$ and $b_i$.

Each of the remaining $Q$ lines contains two space-separated integers $c_j$ and $d_j$.

Print $Q$ lines. On the $k$-th line, print a single integer — the length of the shortest path between houses $c_k$ and $d_k$. Justas measures the distance between two houses as the number of streets that must be traveled.

• $3 \le N \le 200000$
• $1 \le a_i, b_i \le N$ $(1 \le i \le N,\ a_i \ne b_i)$
• $1 \le Q \le 1000000$
• $1 \le c_j, d_j \le N$ $(1 \le j \le Q,\ c_j \ne d_j)$
• From $c_j$ to $d_j$ there is more than one path (not necessarily the shortest) that does not pass through any house more than once.
• From any house you can always reach any other house via the streets.