Distance Queries in a Tree

You are given a tree with N nodes, where each node is uniquely numbered from 1 to N. The tree is provided as a set of N-1 edges. You are also given Q queries. Each query contains two nodes U and V, and your task is to compute the distance between these two nodes. The distance is defined as the number of edges in the unique path connecting the two nodes.

Input Format: The first line of input contains two integers N and Q separated by a space. The next N-1 lines each contain two integers A and B which denote an edge between nodes A and B. The following Q lines each contain two integers U and V, representing a query.

Output Format: For each query, output a single line containing the distance between nodes U and V.

Note: It is guaranteed that the given graph is a tree.

The solution uses the Lowest Common Ancestor (LCA) technique with binary lifting to answer each query efficiently in \( O(\log N) \) time after a \( O(N \log N) \) preprocessing.

inputFormat

The input is provided via standard input (stdin) in the following format:

N Q
A1 B1
A2 B2
... (N-1 lines for edges)
U1 V1
U2 V2
... (Q lines for queries)

Where N is the number of nodes, Q is the number of queries, each edge connects two nodes Ai and Bi, and each query asks for the distance between nodes Ui and Vi.

outputFormat

For each query, print the distance between the given pair of nodes on a separate line to standard output (stdout).

## sample

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

3
3
2

</p>