Planetary Teleportation Distance Calculation

You are given a network of n planets connected by bidirectional teleportation gates forming a tree structure. Since the network is a tree, there is a unique path between any two planets.

For each query, you are given two planets u and v. Your task is to compute the distance between them, where the distance is defined as the number of edges on the unique path connecting u and v.

One useful observation is that if we denote depth(x) as the distance from planet 1 to x and LCA(u,v) as the lowest common ancestor of u and v, then the distance can be calculated using the formula:

\(dist(u,v) = depth(u) + depth(v) - 2 \times depth(\mathrm{LCA}(u,v))\)

Implement an efficient solution to answer all queries.

inputFormat

The input is given via stdin with the following format:

 n q
 u1 v1
 u2 v2
 ...
 u(n-1) v(n-1)
 query_u1 query_v1
 query_u2 query_v2
 ...
 query_uq query_vq

Where:

• n is the number of planets (nodes).
• q is the number of queries.
• Each of the next n-1 lines contains two integers representing a bidirectional edge between two planets.
• Each of the next q lines contains two integers for which the distance needs to be computed.

outputFormat

For each query, output the distance on a new line via stdout.

## sample

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

1
3
2

</p>