graph
You are given a graph ( undirected acyclic graph ) with N nodes. Then you have M queries with 2 numbers, which represent id of 2 nodes. Your task is to find lowest common ancestor for those 2 nodes. Nodes are defined with numbers from 1 to N. Node with id 1 is root of graph.
InputIn first line of input you should read N ( 1 <= N <= 10^6 ), and M ( 1 <= M <= 10^6 ). In next N-1 lines you should read 2 numbers, A and B, and it represent edge between nodes A and B. In next M lines there are 2 numbers, A and B, it is query.
OutputYou should print lowest common ancestor for every query.
Input:
7 3
1 2
1 3
3 4
3 5
5 6
6 7
7 4
6 2
6 7Output:
3
1
6
Image: graph2
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.