Lowest Common Ancestor

Difficulty: 1500 3000 ms 128 MB

trees

The tree is rooted at node 1. For each query (a, b) print their lowest common ancestor.

Input: the first line has N and Q; the next N−1 lines have the edges; the next Q lines each have a query a b.

Output: Q lines with the LCA of each pair.

Constraints:

• 2 ≤ N ≤ 1000
• 1 ≤ Q ≤ 1000

Sample Tests

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

3
1

2 1
1 2
2 2

2

Read the Editorial