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
Manu Narsaria: 2015-01-19 05:17:43

Silly mistakes costed a lot WAs....

Rana Saha: 2015-01-19 05:17:43

Weak Test Cases .. One of my semi-brute force code passed with a very good time .. In fact it's the Top Solution right now.. I can design a test keeping in mind the constraints where that particular code of mine will run out of time.! Test cases should be updated and solutions should be rejudged!

Last edit: 2014-06-12 18:48:53
Hussain: 2015-01-19 05:17:43

O(n logn + q logn) per testcase, and getting TLE :\

Finally AC. I forgot to re-initialize the values for each testcase.

Last edit: 2014-04-19 21:54:29
aristofanis: 2015-01-19 05:17:43

@problemsetter why does O(Q*lgN) time out? Should we use Tarjan's offline algo?

Last edit: 2014-03-23 19:15:44
kayacan: 2015-01-19 05:17:43

1
6
1 2
1 3
1 4
1 5
1 6
0
1
2 3

if get WA try this

adijimmy: 2015-01-19 05:17:43

awesome question loved it learnt a lot from this question :)

DEEPANSHU JAIN: 2015-01-19 05:17:43

Last edit: 2014-02-05 01:30:04
Sameer: 2015-01-19 05:17:43

WA's please check following test cases for the given test case:
3 3 --> 3
3 7 --> 3

Last edit: 2014-01-12 14:24:25
Chandan Mittal: 2015-01-19 05:17:43

whoila !! my soln ranked 3rd :)

Abhishek Gupta: 2015-01-19 05:17:43

come on...printing case is the trick, while the remaining is your concept...3 WA due to "case" :@
best solution in lang C :)

Last edit: 2014-01-15 20:37:56

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