a.cpp

#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long

#define IOS ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

using namespace std;
const int MAXN = 1e6 + 10;
const int INF = 1e9 + 7;
const int EPS = 1e-6;
int timer = 0;

bool upper(int u, int v){
    return (tin[u] <= tin[v] && tout[v] <= tout[u]);
}

void dfs(int v, int pr = 0){
    was[v] = 1;
    tin[v] = ++timer;
    up[v][0] = pr;
    for (int i = 1; i <= L; i++){
        up[v][i] = up[up[v][i - 1]][i - 1];
    }

    for (int to : g[v]){
        if (!was[to]){
            dfs(to, v);
        }
    }
    tout[v] = ++timer;
}

int lca(int a, int b){
    if (upper(a, b)){
        return a;
    }
    if (upper(b, a)){
        return b;
    }
    for (int i = L; i >= 0; i--){
        if (!upper(up[a][i], b)){
            a = up[a][i];
        }
    }

    return up[a][0];
}

void solve(){
    tin[0] = 0;
    tout[0] = INF;

    dfs(1);



}

int main() {
    IOS;
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}