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
tahoangquan2: 2021-03-28 08:38:18

output of the input below:
Case 1:
1
1
3
3
3
3
3
Case 2:
1
Case 3:
3
6
1
7

tahoangquan2: 2021-03-28 08:36:59

i got a lot of wa then figured out by using this test case:
3
7
3 2 3 4
0
3 5 6 7
0
0
0
0
7
1 7
2 7
3 3
3 6
3 7
5 6
5 7
1
0
1
1 1
13
3 2 3 4
0
3 5 6 7
0
0
2 8 9
2 10 11
0
0
2 12 13
0
0
0
4
9 12
8 9
2 11
11 13

Last edit: 2021-03-28 08:39:04
sayskar: 2021-03-07 08:08:18

I am getting an RE .... anyone else also facing the same??

hackerakhil: 2021-02-04 11:57:45

https://www.spoj.com/submit/LCA/id=27389011
Please help i am getting runtime error i have changes constraint of N to 1005,10005,100005 but getting runtime error in all please help me out. Thankx in advance

harshiscoding: 2021-01-23 15:13:42

@up_in_smoke ,use if(n===0) break

princemishra: 2020-12-31 18:35:09

even LCA with O(n) works and rooted at node 1

Last edit: 2020-12-31 18:35:33
wille_25: 2020-12-29 13:48:57

Last edit: 2021-03-15 10:24:56
satyamkr118: 2020-12-27 12:35:12

My 100th one!!

s_tank00_: 2020-10-27 09:24:47

why i m getting a tle please help here's my code
<snip>

[NG]: Read the footer.
https://ideone.com/oO0VZq

Last edit: 2020-10-29 13:47:29
raka143: 2020-08-28 14:12:59

LCA using binary lifting works fine. Took me 0.05s.


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