Lowest Common Ancestor in a Binary Tree

Given a tree with n nodes where the tree is represented by n-1 edges, your task is to answer several queries about the Lowest Common Ancestor (LCA) between two nodes. The tree is undirected and rooted at node 1. For any two nodes \(u\) and \(v\), the LCA is defined as the deepest node (i.e. having maximum depth) which is an ancestor of both \(u\) and \(v\).

The problem can be summarized as follows:

• You are given an integer \(n\), representing the number of nodes in the tree.
• Next, there are \(n-1\) lines each containing two integers \(u\) and \(v\), representing an edge between the nodes \(u\) and \(v\).
• Then, an integer \(q\) denoting the number of queries follows.
• Each of the next \(q\) lines contains two integers \(u\) and \(v\), for which you must compute the LCA.

Assume that the input tree is valid and connected. The calculation of the depth of each node can be done by a Breadth First Search (BFS) starting from the root (node 1). Formally, if \(\text{depth}(x)\) denotes the depth of node \(x\), then for nodes with different depths, the deeper node is lifted along its parent chain until both nodes are at the same depth, and subsequently, they are lifted simultaneously until they meet. This meeting point is the LCA.

Note: All formulas in this description are formatted in \(\LaTeX\); for instance, the depth is denoted as \(\text{depth}(x)\) and the LCA is computed by gradually lifting nodes until they converge.

inputFormat

The input is read from stdin and has the following format:

 n
 u1 v1
 u2 v2
 ...
 u(n-1) v(n-1)
 q
 a1 b1
 a2 b2
 ...
 aq bq

Where:

• n (\(1 \leq n \leq 10^5\)): The number of nodes in the tree.
• Each of the next \(n-1\) lines contains two integers \(u\) and \(v\), denoting an undirected edge between nodes.
• q: The number of LCA queries.
• Each of the following \(q\) lines contains two integers \(a\) and \(b\) for which you need to determine the LCA.

outputFormat

For each query, output the LCA as an integer on a new line to stdout.

## sample

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

2
1
3

</p>