LCA Queries using BINARY LIFTING

/*
Que_link- https://www.spoj.com/problems/LCA/

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.
                                                 1
                                              /  |  \
                                             2   3   4
                                              /  | \____
                                             5   6      7
                                               /  \    /  \
                                              8    9  10   11
                                                      / \
                                                     12 13
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
*/

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

int dp[1001][11];
int level[1001];
list<int>* adj;
int parent[1001];

void DFS(int node, int depth){
    level[node]=depth;
    for(auto nei: adj[node]){
        DFS(nei,depth+1);
    }
}

void precomputation(int n){
    for(int node=1;node<=n;node++){
        dp[node][0]=parent[node];
    }
    for(int node=1;node<=n;node++){
        for(int jump=1;jump<11;jump++){
            if(dp[node][jump-1]!=-1){
                dp[node][jump]=dp[dp[node][jump-1]][jump-1];
            }
        }
    }
}

void moveUP(int &node, int k){
    for(int jump=10;jump>=0;jump--){
        if(k>=pow(2,jump)){
            k-=pow(2,jump);
            node=dp[node][jump];
            if(node==-1){
                return;
            }
        }
    }
}

int LCA(int node1, int node2){
    if(level[node1]>level[node2]){
        moveUP(node1,level[node1]-level[node2]);
    }
    if(level[node1]<level[node2]){
        moveUP(node2,level[node2]-level[node1]);
    }
    if(node1==node2){
        return node1;
    }
    for(int jump=10;jump>=0;jump--){
        if(dp[node1][jump]!=-1 && dp[node1][jump]!=dp[node2][jump]){
            node1=dp[node1][jump];
            node2=dp[node2][jump];
        }
    }
    return dp[node1][0];
}


void solve(){
    int N;
    cin>>N;
    adj=new list<int>[N+1];
    for(int node=1;node<=N;node++){
        int m;
        cin>>m;
        int in;
        while(m--){
            cin>>in;
            adj[node].push_back(in);
            parent[in]=node;
        }
    }
    DFS(1,1);
    precomputation(N);
    int q;
    cin>>q;
    while(q--){
        int node1,node2;
        cin>>node1>>node2;
        cout<<LCA(node1,node2)<<endl;
    }
}

int main(){
    int TC;
    cin>>TC;
    int num=1;
    while(TC--){
        memset(dp,-1,sizeof(dp));
        memset(parent,-1,sizeof(parent));
        memset(level,0,sizeof(level));
        cout<<"Case "<<num++<<":"<<endl;
        solve();
    }
}