LCA using Segment Tree

//LCA using Segment Tree
//https://www.spoj.com/problems/LCA/
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;

#define mem(dp,a)           memset(dp,a,sizeof dp)
#define rep(i,a,b)          for(ll i=a;i<b;i++)
#define pb(x)               push_back(x)
#define mp(x,y)             make_pair(x,y)
#define fastio              ios_base::sync_with_stdio(false);cin.tie(NULL)
#define F                   first
#define S                   second
#define all(v)              (v).begin(),(v).end()
#define pi                  3.14159265359
ll INF=1e18+10;
ll MOD=1000000009;

const int N=1e4+10;
vector<int> euler,adj[N];
int first[N],segt[4*N],height[N];
bool vis[N];

void dfs(int v,int h=0)
{
    vis[v]=true;euler.push_back(v);
    first[v]=euler.size()-1,height[v]=h;
    for(auto to : adj[v])
        if(!vis[to])
            dfs(to,h+1),euler.push_back(v);
}

void build(int l,int r,int v)
{
    if(l==r)
        segt[v]=euler[l];
    else
    {
        int mid=(l+r)>>1;
        build(l,mid,v<<1);
        build(mid+1,r,v<<1|1);
        int left=segt[v<<1],right=segt[v<<1|1];
        segt[v]=(height[left]<height[right]) ? left : right;
    }
}

int query(int v,int l,int r,int L,int R)
{
    if(l>R || r<L)
        return -1;
    if(l<=L && R<=r)
        return segt[v];
    int mid=(L+R)>>1;
    int left=query(v<<1,l,r,L,mid);
    int right=query(v<<1|1,l,r,mid+1,R);
    if(left==-1)return right;
    if(right==-1)return left;
    return (height[left]<height[right]) ? left : right;
}

int lca(int u,int v)
{
    int left=first[u],right=first[v];
    if(left>right)swap(left,right);
    return query(1,left,right,1,euler.size()-1);
}

int main()
{
    fastio;
    int t;cin>>t;
    for(int j=1;j<=t;j++)
    {
        cout<<"Case "<<j<<":\n";
        mem(segt,0);mem(vis,0);mem(first,0);mem(height,0);
        euler.clear();euler.push_back(-1);
        for(int i=0;i<N;i++)adj[i].clear();
        int n;cin>>n;
        for(int i=1;i<=n;i++)
        {
            int m;cin>>m;
            int b;
            for(int j=0;j<m;j++)
                cin>>b,adj[i].push_back(b);
        }
        dfs(1,0);
        build(1,euler.size()-1,1);
        int q;cin>>q;
        while(q--)
        {
            int u,v;cin>>u>>v;
            cout<<lca(u,v)<<"\n";
        }
    }
}