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
mr_pandey: 2019-01-24 02:22:19

Take care of the queries where entry time of vertex v in euler path is less than that of vertex u
Looping : 0.22
Segtree : 0.15

amitnsky: 2019-01-05 17:48:02

Last edit: 2019-01-05 17:49:00
jvjplus: 2018-12-27 08:53:41

naive: 0.36
sqrt 0.16
binary Lifting 0.17

Last edit: 2018-12-27 19:55:02
r_ash: 2018-10-30 12:40:37

take care when v and w are the same

phoemur: 2018-10-09 22:42:24

Weak test cases. O(n) queries accepted

tanardi gunawan: 2018-10-03 13:40:07

AC IN ONE GO !!!!

cowshinafk: 2018-09-23 05:46:07

My first hit get WA 'cause i set all my array with the size of 1015, then i lift to 10015 and got AC.

Last edit: 2018-09-23 05:46:22
himanshu pal: 2018-08-31 05:01:06

Strange if I am using printf("%d\n", LCA(u, v)); Then it is giving me right answer and if I am using same code with no change but with cout << LCA(u,v) << endl; it gives me wrong answer Can anyone help me figure out what could be wrong here.

aman_sachin200: 2018-06-19 13:35:26

Did Using Euler Tour+RMQ!!!

javier_dlg96: 2018-04-14 00:44:12

For those with runtime errors, try setting maxN to something higher than what the problem states.


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