LCA_SPOJ

#include<bits/stdc++.h>
using namespace std;


#define pb push_back
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define M 100007
#define INF 1e9
#define INFL 1e18
#define PI acos(-1)
#define mp make_pair
#define fast_in_out ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//const int fx[]= {+1,-1,+0,+0};
//const int fy[]= {+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
#define MX 1010
vector<int>adj[MX];
int L[MX];
int SparseTable[MX][22];
int T[MX];

void dfs(int from,int u,int depth)
{
    T[u]=from;
    L[u]=depth;
    for(int i=0;i<adj[u].size();i++)
    {
        int v=adj[u][i];
        if(v==from)
            continue;
        dfs(u,v,depth+1);
    }

}


void LCA_initialize(int N)
{
    memset(SparseTable,-1,sizeof SparseTable);
    int i,j;
    for(i=0;i<N;i++)
    {
        SparseTable[i][0]=T[i];
    }
    for(j=1;(1<<j)<N;j++)
    {
        for(i=0;i<N;i++)
        {
            if(SparseTable[i][j-1]!=-1)
            {
                SparseTable[i][j]=SparseTable[SparseTable[i][j-1]][j-1];
            }
        }
    }
}


int LCA_query(int N,int p,int q)
{
    int tmp,log,i;
    if(L[p]<L[q])
    {
        tmp=p;
        p=q;
        q=tmp;
    }
    log=1;
    while(true)
    {
        int next=log+1;
        if((1<<next)>L[p])
            break;
        log++;
    }

    for(i=log;i>=0;i--)
    {
        if(L[p]-(1<<i)>=L[q])
        {
            p=SparseTable[p][i];
        }
    }
    if(p==q)
        return p;
    for(i=log;i>=0;i--)
    {
        if(SparseTable[p][i]!=-1 && SparseTable[p][i]!=SparseTable[q][i])
        {
            p=SparseTable[p][i];
            q=SparseTable[q][i];
        }
    }
    return T[p];


}

int main()
{
    fast_in_out;
    int kase=0;
    int q;
    cin>>q;
    while(q--)
    {

    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int m;
        cin>>m;
        for(int j=0;j<m;j++)
        {
            int x;
            cin>>x;
            x--;
            adj[i].pb(x);

        }
    }


    dfs(-1,0,0);
    LCA_initialize(n);

    int q;
    cin>>q;
    cout<<"Case "<<kase+1<<":"<<endl;
    kase++;
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        x--;
        y--;
        int ans=LCA_query(n,x,y);
        cout<<ans+1<<endl;
    }
    for(int i=0;i<MX;i++)
    {
        T[i]=0;
        L[i]=0;
        adj[i].clear();
    }


    }
    return 0;
}