LCA

//LCA:Lowest Common Anchester:
#include <bits/stdc++.h>
using namespace std;
#define Size 100005

vector<int> Graph[Size];
vector< vector<int> > sparseTable;
vector<int> discTime,finishTime;
int u,v,N,Query,edge;
int Time = 0,level = 0;

void DFS(int cur,int prev){
    discTime[cur] = ++Time;
    sparseTable[cur][0] = prev;
    for(int c = 1;c<=level;c++){
        sparseTable[cur][c] = sparseTable[sparseTable[cur][c-1]][c-1];
    }
    for(int i = 0;i<(int)Graph[cur].size();i++){
        int adj = Graph[cur][i];
        if(adj != prev){
            DFS(adj,cur);
        }
    }
    finishTime[cur] = ++Time;
}

bool isUpper(int u,int v){
    return (discTime[u] <= discTime[v]) && (finishTime[u] >= finishTime[v]);
}

void process(){
    sparseTable.resize(N);
    discTime.resize(N);
    finishTime.resize(N);
    level = 1,Time = 0;
    while((1<<level) <= N){
        level++;
    }
    for(int i = 0;i<N;i++){
        sparseTable[i].resize(level+1);
    }
    DFS(0,0);
}

int LCA(int n1,int n2){
    if(isUpper(n1,n2)) return n1;
    if(isUpper(n2,n1)) return n2;
    for(int c = level;c>=0;c--){
        if(!isUpper(sparseTable[n1][c],n2)){
            n1 = sparseTable[n1][c];
        }
    }
    return sparseTable[n1][0];
}

int main() {
    scanf("%d %d",&N,&edge);
    for(int i = 0;i<edge;i++){
        scanf("%d %d",&u,&v);
        Graph[u].push_back(v);
        Graph[v].push_back(u);
    }
    process();
    scanf("%d",&Query);
    for(int i = 0;i<Query;i++){
        scanf("%d %d",&u,&v);
        int lca = LCA(u,v);
        printf("LCA of node %d and node %d = %d\n",u,v,lca);
    }
    return 0;
}