LCASQ - Lowest Common Ancestor

You are given a rooted tree and an ordered list of queries. Each query is specified by two nodes u and v and the answer to a query is the lowest common ancestor of u and v.

Recall that the Lowest Common Ancestor of two nodes is the node that is furthest from the root and also an ancestor of the two nodes. In this problem we use the convention that a node is in fact an ancestor of itself.

Input

The first line contains an integer N, the number of nodes in the tree (N <= 10000). Each of the next N lines will start with a number M the number of child nodes of the Nth node, (0 <= M <= 999) followed by M numbers the child nodes of the Nth node. Nodes will be labeled from 0 to N-1. Following will be a number Q, the number of queries that will be asked (Q <= 10000).  Each of the next Q lines will have two numbers u and v (0 <= u, v < N) which specify the parameters of that specific query.

The root of the tree will always be node 0.

Output

For each query output the answer on its own line. Answers should follow the same order as given in the input.

Example

Input:
3
2 1 2
0

3
1 2
1 1
2 2  Output: 0
1

Added by:Joshua Kirstein
Date:2014-10-20
Time limit:12s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2024-07-19 20:03:17
i think if spoj wants to be famous for good problems these 800 rated problems should be erased from it
2021-07-23 13:24:58
Only difference here from the other LCA problem is node are unordered i.e. node 99 can have a descendant node 1.
2021-06-05 21:56:33
Sample OP lol
2021-03-22 10:32:38
Finding LCA using binary lifting would do the job.
2020-09-04 10:45:37
why novie approach wont work?
2020-08-23 09:58:28
Novice approach won't work this time. Implement Binary lifting
2017-05-30 11:11:30
Same as LCA :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.