LogiQuest
PrevNext

293. Lowest Common Ancestor

HardTreesLCA

The tree is rooted at node 1. Answer q queries: print the lowest common ancestor of u and v.

Input format

Line 1: n Next n − 1 lines: u v Next line: q Next q lines: u v

Output format

One LCA per line.

Example 1

Input

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

Output

2
1
3
2

Example 2

Input

1
1
1 1

Output

1

Constraints

1 ≤ n, q ≤ 10⁵

Read input from standard input and print the answer to standard output. Your code is judged against 3 test cases, most of them hidden.

Loading the MyLoginn IDE…