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 N1. 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
0
3
1 2
1 1
2 2
Output: 0
1
2
hide comments
anshjain18:
20200904 10:45:37
why novie approach wont work? 

tejameranaam:
20200823 09:58:28
Novice approach won't work this time. Implement Binary lifting 

rraj001:
20170530 11:11:30
Same as LCA :) 
Added by:  Joshua Kirstein 
Date:  20141020 
Time limit:  12s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 