Algo pro1 O(NLogN + QLogN)

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

typedef pair<int,int> ii;
const int N = 1e5 + 5e1;
#define OO INT_MAX
#define S second
#define F first

int Tree[N][2] ,Par[N] ,idx[N];
int n ,Q;

int DfsSpTree[N * 2][2]; /// DFS Spanning Tree
int DfsSize = 1;    /// DFS Spanning Tree Size

const int Log = (int)log2(N*2);
ii MinSpTable[N * 2][Log];
int AncOfNodes[N][Log];

void Dfs_Pre_Order(int u = 1 ,int Depth = 1) {
        DfsSpTree[ DfsSize ][0] = u;
        DfsSpTree[ DfsSize ][1] = Depth;

        idx[u] = DfsSize;
        DfsSize ++;

        for(int j = 0 ; j < 2 ; j++){
                int v = Tree[u][j];
                if( v != -1 ){
                        Dfs_Pre_Order(v ,Depth + 1);
                        DfsSpTree[ DfsSize ][0] = u;
                        DfsSpTree[ DfsSize ][1] = Depth;
                        DfsSize++;
                }
        }
}

void FillSparseTable(int Size ,int Log) {
        for(int i = 0 ; i <= Size ; i++)
                for(int j=0 ; j <= Log ; j++)
                        MinSpTable[i][j] = ii(-1 ,OO);

        for(int i = 1 ; i < Size  ; i++)
                MinSpTable[i][0] = ii(DfsSpTree[i][0] , DfsSpTree[i][1]);
        for(int j = 1 ; j <= Log ; j++){
                int Rang = (1 << j);
                int Mid  = (Rang >> 1);
                for(int i = 1 ; i + Rang - 1 < Size ; i++) {
                        if( MinSpTable[i][j - 1].S < MinSpTable[i + Mid][j - 1].S )
                             MinSpTable[i][j] = MinSpTable[i][j - 1];
                        else MinSpTable[i][j] = MinSpTable[i + Mid][j - 1];
                }
        }
}

ii GetAncestor(int L ,int R) {
        int Rang = R - L + 1;
        int K = (int)log2( Rang );

        ii Res = ii(OO ,OO);
        if( MinSpTable[L][K].S <= MinSpTable[R - (1 << K) + 1][K].S )
             Res = MinSpTable[L][K];
        else Res = MinSpTable[R - (1 << K) + 1][K];

        return Res;
}

void FillAncsOfNodes(int n ,int Log) {
        for(int i = 0 ; i <= n ; i++)
                for(int j=0 ; j <= Log ; j++)
                        AncOfNodes[i][j] = 1;

        for(int i = 1 ; i <= n ; i++)
                AncOfNodes[i][0] = Par[i];
        for(int j = 1 ; j <= Log ; j++)
                for(int i = 1 ; i <= n ; i++)
                        AncOfNodes[i][j] = AncOfNodes[ AncOfNodes[i][j - 1] ][j - 1];
}

int GoTopTo(int u ,int k){
        int Res = u;
        while( k ){
            int Log = (int)log2(k);
            Res = AncOfNodes[Res][Log];
            k -= (1 << Log);
        }
        return Res;
}

void Memset(int n) {
    for(int i = 0 ; i <= n ; i++) idx[i] = -1;
}

/// ------------------------------------------------------------------ ///

void SolveQuery() {
        int u ,v;
        scanf("%d%d" ,&u ,&v);

        int L = idx[u] ,R = idx[v];
        if( L > R )swap(L ,R);
        ii Ancestor = GetAncestor(L ,R);

        int AncHigh = DfsSpTree[ idx[Ancestor.F] ][1] ,
            Uhigh   = DfsSpTree[ idx[u] ][1],
            Vhigh   = DfsSpTree[ idx[v] ][1];

        int Ans = -1;
        if( Uhigh == Vhigh ) {
                Ans = Ancestor.F;
        } else if( Uhigh > Vhigh ) {
                int Diff = Vhigh - AncHigh;
                int DepthOfAns = (AncHigh + (Uhigh - Diff)) >> 1;
                int Kth_Anc = Uhigh - DepthOfAns;
                Ans = GoTopTo(u ,Kth_Anc);
        } else if( Uhigh < Vhigh ) {
                int Diff = Uhigh - AncHigh;
                int DepthOfAns = (AncHigh + (Vhigh - Diff)) >> 1;
                int Kth_Anc = Vhigh - DepthOfAns;
                Ans = GoTopTo(v ,Kth_Anc);
        }

        printf("%d\n" ,Ans);
}

int main() {
        scanf("%d" ,&n);
        for(int i=1 ; i <= n ; i++) {
                int L ,R; scanf("%d%d" ,&L ,&R);
                Tree[i][0] = L;
                Tree[i][1] = R;
                Par[L] = Par[R] = i;
        }

        Memset(n + 1);
        Dfs_Pre_Order();
        FillSparseTable(DfsSize ,(int)log2(DfsSize));
        FillAncsOfNodes(n , (int)log2(n));

        scanf("%d" ,&Q);
        while( Q-- ) SolveQuery();
    return 0;
}