Shortest Path in a Tree

You are given a tree with n nodes and n - 1 edges. The tree is undirected and connected. Your task is to answer q queries. For each query, compute the shortest path length between two given nodes u and v.

The distance between any two nodes is defined as the number of edges on the unique simple path connecting them. In other words, if there is a unique path from u to v, then the answer for that query is:

$$d(u,v) = \text{number of edges on the unique path connecting } u \text{ and } v. $$

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

n q
u1 v1
u2 v2
... (n-1 lines representing tree edges)
q1_u q1_v
q2_u q2_v
... (q lines representing the queries)

Here, n is the number of nodes, and q is the number of queries. Each of the next n - 1 lines contains two integers representing an edge between nodes. The subsequent q lines each contain two integers representing the nodes for which you need to compute the shortest path length.

outputFormat

For each query, output the shortest path length on a separate line to standard output (stdout).

## sample

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

3
3
2

</p>