LCA - Lowest Common Ancestor

no tags 

A tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree. - Wikipedia 

The lowest common ancestor (LCA) is a concept in graph theory and computer science. Let T be a rooted tree with N nodes. The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself). - Wikipedia

Your task in this problem is to find the LCA of any two given nodes v and w in a given tree T.

For example the LCA of nodes 9 and 12 in this tree is the node number 3.

Input

The first line of input will be the number of test cases. Each test case will start with a number N the number of nodes in the tree, 1 <= N <= 1,000. Nodes are numbered from 1 to N. The next N lines each one 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. The next line will be a number Q the number of queries you have to answer for the given tree T, 1 <= Q <= 1000. The next Q lines each one will have two number v and w in which you have to find the LCA of v and w in T, 1 <= v, w <= 1,000.

Input will guarantee that there is only one root and no cycles.

Output

For each test case print Q + 1 lines, The first line will have “Case C:” without quotes where C is the case number starting with 1. The next Q lines should be the LCA of the given v and w respectively.

Example

Input:
1
7
3 2 3 4
0
3 5 6 7
0
0
0
0
2
5 7
2 7

Output:
Case 1:
3
1

hide comments
manimanimani: 2020-05-15 21:29:24

probably the best problem for learning LCA!

shrey_devep: 2020-05-14 15:51:33

Take Care of long long and for binary lifting intialisation of 2D lifting array

Last edit: 2020-05-14 16:09:37
abid_jawad: 2020-04-03 21:35:49

maybe the constraint of N is wrong in the question, got wa, then simply submitted again by increasing the value of n, got ac

fahimcp495: 2020-03-31 21:43:17

Required time for various technique using fast I/O:
1. Naive Approach- preprocess: O(N), Query: O(N^2)--------------------------------0.23s
2. using Square Root Decomposition: preprocess: O(N), Query: O(sqrt(N))--0.04s
3. using Segment Tree: preprocess: O(NlogN), Query: O(logN)-------------------0.02s
4. using Sparse Table: preprocess: O(NlogN), Query: O(1)-------------------------0.04s
5. Binary Lifting: preprocess: O(N), Query: O(logN)-----------------------------------0.03s
6. Farach Colton and Bender Algorithm: preprocess: O(N), Query: O(1)------0.03s
7. Tarjan's Offline Algorithm: preprocess: O(N), Query: O(l1)---------------------0.03s

bhavyarustgi10: 2020-03-31 08:00:17

What root we have to consider

sagsango: 2020-03-30 14:03:48

Try it :-) https://www.codechef.com/problems/TALCA
suggested by darkhire21

manish_thakur: 2020-03-30 11:49:35

was getting compilation error due to some comments in the code, removed them and got AC!

vineetjai: 2020-01-18 15:44:59

Binary Lifting

ahmet25: 2019-12-26 21:36:54

euler tour+segment tree works 0.05s ~ 26mb

wolf3h2h2: 2019-12-19 00:27:59

if you are getting wa check this case
1
1
0
1
1 1


Added by:hossamyosef
Date:2013-05-13
Time limit:0.600s-1.113s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:FCIS/ASU Local Contest 2013