Least Common Ancestor in a Tree

You are given a rooted tree with n nodes numbered from 1 to n, where node 1 is the root. The tree is described by its n-1 edges. You are also given q queries. In each query, you are provided with two nodes, u and v, and you must determine their Least Common Ancestor (LCA), i.e. the deepest node that is an ancestor of both u and v.

This problem requires efficient LCA computation. A common approach is to preprocess the tree using a breadth-first search from the root and then apply binary lifting (dynamic programming) to answer each query in O(log n) time.

Note: All formulas, if any, use LaTeX format. For example, the height of the binary lifting table is given by \(\lceil \log_2(n) \rceil\).

inputFormat

The input is given via standard input and has the following format:

<n>
<u1> <v1>
<u2> <v2>
... (n-1 lines representing edges)
<q>
<u1> <v1>
<u2> <v2>
... (q lines representing queries)

Here, n is the number of nodes in the tree, each edge connects nodes u and v, and q is the number of queries.

outputFormat

For each query, output a single line containing the LCA of the two given nodes.

## sample

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

2
1
1

</p>