<PREV Problem:
NEXT>
Solved by 148 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

LCA problem

Time limit = 4 second(s)

Memory limit = 40 Mb

Given a tree description your program should answer series of LCA-queries:

LCA(u,v) == lowest common ancestor for nodes $u$ and $v$.

Input

The first line contains number of edges $E$. Next $E$ lines contain edge descriptions. Each description is

 vertext_id parent_vertex_id

Root has id equal to 0.

E ≤ 400000.

Next line contains number of queries $M$. M ≤ 400000. Then $M$ line follow with LCA-queries descriptions. Each description is two vertex ids $u$ and $v$ delimited by space.

Output

Output $M$ lines with answers (verteces ids) to the given $M$ LCA-queries.

Input#1
10
1 0
2 1
3 1
4 2
5 2
6 3
7 3
8 6
9 7
10 7
4
8 10
2 5
4 5
6 9
Output#1
3
2
2
3

Author:
Tests and description by Vyacheslav Simonenko.
20 May 2007

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 210ms

SW soft NIX
ID = 54.81.197.127