GUIDE

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

const int N = 2e5 + 5;
const int M = log2(N) + 1;

int n, l;
vector<int> a[N];

int timer;
int t_in[N], t_out[N];
int up[N][M];

void DFS(int v, int p) {
    t_in[v] = ++timer;
    up[v][0] = p;

    for(int i = 1; i <= l; ++i)
        up[v][i] = up[up[v][i-1]][i-1];

    for(int u : a[v])
        if(u != p) DFS(u, v);
    t_out[v] = ++ timer;
}

bool is_ancestor(int u, int v) {
    return t_in[u] <= t_in[v] && t_out[u] >= t_out[v];
}

int LCA(int u, int v) {
    if(is_ancestor(u, v)) return u;
    if(is_ancestor(v, u)) return v;

    for(int i = l; i >= 0; --i)
        if(!is_ancestor(up[u][i], v))
            u = up[u][i];

    return up[u][0];
}

int main()
{
    freopen("GUIDE.inp", "r", stdin);
    freopen("GUIDE.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    for(int i = 1; i <= n-1; ++i){
        int u, v; cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    timer = 0;
    l = log2(n);
    DFS(1, 1);

    int t; cin >> t;
    while(t--) {
        int u, v; cin >> u >> v;

        int lca = LCA(u, v);

        if(u != lca)
            cout << up[u][0] << '\n';
        else {
            for(int i = l; i >= 0; --i) {
                if(up[v][i] == 0) continue;

                if(!is_ancestor(up[v][i], u))
                    v = up[v][i];
            }

            cout << v << '\n';
        }
    }
    return 0;
}