This page is still under construction.

Parts of this page are still being built. What you see may change.

Lowest Common Ancestor 2

Interview

Time limit1.5sMemory limit256 MB

Summary
Given a rooted tree with up to 100,000 nodes, answer up to 100,000 lowest common ancestor queries.
Level

Medium4 of 10

Topics
Tree, DFS
Solved
No attempts yet

Problem

A tree with NN vertices is given (2≤N≤100,0002 \le N \le 100{,}000). The vertices are numbered 1 to NN, and vertex 1 is the root.

You are given MM pairs of nodes (1≤M≤100,0001 \le M \le 100{,}000). For each pair, print the number of the lowest common ancestor of the two nodes. Among all common ancestors of the two nodes, the lowest common ancestor is the one farthest from the root.

A vertex is an ancestor of itself. So if one vertex of a pair is an ancestor of the other, the answer is that ancestor.

Input

The first line contains the number of nodes NN. Each of the next N−1N-1 lines contains the numbers of two vertices that are connected in the tree. The two vertices on a line are not necessarily written in parent, child order.

The next line contains the number of pairs MM, and each of the following MM lines contains one pair of vertices whose lowest common ancestor you must find.

Output

Print MM lines. On each line print the number of the lowest common ancestor of the corresponding pair, in the order the pairs are given.

Examples2

  1. Example 1

    Input
    15
1 2
1 3
2 4
3 7
6 2
3 8
4 9
2 5
5 11
7 13
10 4
11 15
12 5
14 7
6
6 11
10 9
2 6
7 6
8 13
8 15
    Expected output
    2
4
2
1
3
1

  2. Example 2

    Input
    2
2 1
1
1 2
    Expected output
    1