Lowest Common Ancestor in a Tree

You are given a tree with n nodes rooted at node 1 and q queries. For each query, you need to compute the lowest common ancestor (LCA) of a given pair of nodes. The LCA of two nodes u and v in a tree is the deepest node that is an ancestor of both u and v.

Input and Output (formal):

• Input: The first line contains two integers n and q, representing the number of nodes and the number of queries respectively. The next n-1 lines each contain two integers u and v, representing an undirected edge between nodes u and v. The following q lines each contain two integers representing a query for the LCA of the given two nodes.
• Output: For each query, output the LCA of the given nodes on a separate line.

Use the standard binary lifting technique to implement this efficiently. In mathematical notation, given the depth d of each node, the parent matrix P is computed using the recurrence:

[ P[i][j] = \begin{cases} -1 & \text{if } i = 0 \text{ and node } j \text{ has no parent},\ P[i-1][P[i-1][j]] & \text{if } P[i-1][j] \neq -1. \end{cases} ]

Your code must read from standard input (stdin) and write to standard output (stdout).

inputFormat

The input consists of multiple lines:

• The first line contains two integers n and q separated by a space.
• The next n-1 lines each contain two integers u and v, indicating an edge between nodes u and v.
• The following q lines each contain two integers representing a query for which you need to find the LCA.

outputFormat

For each query, output the lowest common ancestor on a separate line.

## sample

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

2
1
3

</p>