#include "algo.h"
#include <iostream>
#include <fstream>
 
void recursiveDfs (int &node, int &level, std::vector<int> &eulerRep,
    std::vector<int> &levelEvidence, int *firstOccourance,
    std::vector<std::vector<int>> &graph, int &fromNode) {
 
    eulerRep.push_back(node);
    levelEvidence.push_back(level);
    firstOccourance[node] = eulerRep.size() - 1;
 
    for (unsigned int i = 0; i < graph[node].size(); ++i) {
        if (graph[node][i] == fromNode)
            continue;
 
        int nextLevel = level + 1;
        recursiveDfs(graph[node][i], nextLevel, eulerRep, levelEvidence,
            firstOccourance, graph, node);
 
        eulerRep.push_back(node);
        levelEvidence.push_back(level);
    }
}
 
void makeRmq(int **rmq, const int &sizeOfRmq, std::vector<int> &levelEvidence, int *lg) {
    int lgIdx;
 
    for (int i = 2; i <= sizeOfRmq; ++i) {
        lg[i] = lg[i >> 1] + 1;
    }
    for (int i = 1; i <= sizeOfRmq; ++i) {
        rmq[0][i] = i;
    }
 
    for (int i = 1; (1 << i) < sizeOfRmq; ++i) {
        for (int j = 1; j <= sizeOfRmq - (1 << i); ++j) {
            lgIdx = 1 << (i - 1);
            rmq[i][j] = rmq[i - 1][j];
            if (levelEvidence[rmq[i][j]] > levelEvidence[rmq[i - 1][j + lgIdx]]) {
                rmq[i][j] = rmq[i - 1][j + lgIdx];
            }
        }
    }
}
 
int getLca(int &node1, int &node2, int *firstOccourance, int *lg,
    std::vector<int> &eulerRep, std::vector<int> &levelEvidence, int **rmq) {
 
    int oc1 = firstOccourance[node1];
    int oc2 = firstOccourance[node2];
 
    if (oc1 > oc2){
        oc1 = oc1 ^ oc2;
        oc2 = oc1 ^ oc2;
        oc1 = oc1 ^ oc2;
    }
 
    int dif = oc2 - oc1 + 1;
    int lgIdx = lg[dif];
    int sol = rmq[lgIdx][oc1];
    int shift = dif - (1 << lgIdx);
 
    if (levelEvidence[sol] > levelEvidence[rmq[lgIdx][oc1 + shift]])
        sol = rmq[lgIdx][oc1 + shift];
 
    return eulerRep[sol];
}
 
std::vector<int> lca(std::vector<std::vector<int>> &graph,
    std::vector< std::pair<int, int> > &queries) {
 
    std::vector<int> eulerRep, levelEvidence, ans;
 
    eulerRep.push_back(0);
    levelEvidence.push_back(0);
 
    int *firstOccourance;
    int node = 1, level = 0, **rmq, *lg;
 
    firstOccourance = new int [graph.size()];
    rmq = new int* [24];
    for (int i = 0; i < 24; ++i) {
        rmq[i] = new int [200005] {0};
    }
 
    recursiveDfs(node, level, eulerRep, levelEvidence, firstOccourance, graph, level);
 
    lg = new int [eulerRep.size() + 1] {0};
 
    makeRmq(rmq, eulerRep.size(), levelEvidence, lg);
 
    for (unsigned int i = 0; i < queries.size(); ++i) {
        ans.push_back(getLca(queries[i].first, queries[i].second,
            firstOccourance, lg, eulerRep, levelEvidence, rmq));
    }
 
    return ans;
 
}