Tree Distance Queries

You are given a tree with ( n ) nodes labeled from 1 to ( n ) and ( n-1 ) edges. The tree is undirected and connected. For each of the ( q ) queries, you are provided two nodes and must determine the distance between them, defined as the number of edges on the unique path connecting the two nodes. The tree is rooted at node 1 for the purpose of computation.

This problem requires efficient processing of multiple queries. A common technique is to preprocess the tree (using a Breadth-First Search, for example) to compute the parent and depth of each node, and then to answer each query using a Lowest Common Ancestor (LCA) method. The LCA of two nodes ( u ) and ( v ) is the deepest node that is an ancestor of both ( u ) and ( v ). The distance between ( u ) and ( v ) can be computed using the formula: [ \text{distance}(u,v) = \text{depth}[u] + \text{depth}[v] - 2 \times \text{depth}[\text{LCA}(u,v)] ]

Note: All formulas are expressed in LaTeX format.

inputFormat

The input is provided via stdin and has the following format:

• The first line contains two integers ( n ) and ( q ): the number of nodes in the tree and the number of queries.
• The next ( n-1 ) lines each contain two integers ( u ) and ( v ), indicating that there is an edge between nodes ( u ) and ( v ).
• The following ( q ) lines each contain two integers ( a ) and ( b ), representing a query that asks for the distance between node ( a ) and node ( b ).

outputFormat

For each query, output a single integer representing the distance between the two queried nodes. Each answer should be printed on a new line to stdout.## sample

7 3
1 2
1 3
2 4
2 5
3 6
3 7
4 5
4 6
6 7

2
4
2