struct HLD {
    /*
    使用树链剖分求 LCA, HLD tree(edge, 1) -> 初始化
    tree.lca(u, v) -> 求 u, v 的最近公共祖先
    */
    const std::vector<std::vector<int>> &edge;

    std::vector<int> fa, dep, son, sz, top;

    HLD(const std::vector<std::vector<int>> &edge_, int root = 1) : edge(edge_) {
        int n = (int)edge.size() - 1;
        fa.assign(n + 1, 0), dep.assign(n + 1, 0), son.assign(n + 1, 0), sz.assign(n + 1, 0), top.assign(n + 1, 0);

        dfs1(root, 0);
        dfs2(root, root);
    }

    int lca(int u, int v) const {
        while (top[u] != top[v]) {
            if (dep[top[u]] < dep[top[v]]) {
                std::swap(u, v);
            }
            u = fa[top[u]];
        }
        return dep[u] < dep[v] ? u : v;
    }

private:
    void dfs1(int u, int f) {
        fa[u] = f, dep[u] = dep[f] + 1, sz[u] = 1, son[u] = 0;
        for (auto v : edge[u]) {
            if (v == f) {
                continue;
            }
            dfs1(v, u);
            sz[u] += sz[v];
            if (sz[son[u]] < sz[v]) son[u] = v;
        }
    }

    void dfs2(int u, int t) {
        top[u] = t;
        if (son[u] == 0) {
            return;
        }
        dfs2(son[u], t);
        for (auto v : edge[u]) {
            if (v == fa[u] || v == son[u]) {
                continue;
            }
            dfs2(v, v);
        }
    }
};

std::vector<int> e[N];
int fa[N], dep[N], son[N], sz[N], top[N];
int n, m, s;

void dfs1(int u, int father)
{
	fa[u] = father;
	dep[u] = dep[father] + 1;
	sz[u] = 1;
	for (auto to : e[u])
	{
		if (to == father)
			continue;
		dfs1(to, u);
		sz[u] += sz[to];
		if (sz[son[u]] < sz[to])
			son[u] = to;
	}
}

void dfs2(int u, int t)
{
	top[u] = t;
	if (son[u] == 0)
		return;
	dfs2(son[u], t);
	for (auto to : e[u])
	{
		if (to == fa[u] || to == son[u])
			continue;
		dfs2(to, to);
	}
}

int LCA(int u, int v)
{
	while (top[u] != top[v])
	{
		if (dep[top[u]] < dep[top[v]])
			std::swap(u, v);
		u = fa[top[u]];
	}
	return dep[u] < dep[v] ? u : v;
}

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

/*
  Heavy-Light Decomposition (HLD) for LCA (and a few utilities)
  -------------------------------------------------------------
  Usage:
    HLD hld(n);
    for (...) hld.addEdge(u, v);
    hld.build(root);               // default root = 1

    int w = hld.lca(u, v);
    int d = hld.dist(u, v);
    bool anc = hld.isAncestor(u, v); // u is ancestor of v ?

  Notes:
    - 1-indexed.
    - Recursion depth is O(n) in worst-case chains. If your judge is strict,
      compile with bigger stack or convert dfs to iterative.
*/

struct HLD {
    int n, root;
    vector<vector<int>> g;

    // per-node data
    vector<int> parent;   // parent[u]
    vector<int> depth;    // depth from root
    vector<int> heavy;    // heavy child of u (or -1)
    vector<int> sz;       // subtree size
    vector<int> head;     // head (top) of the heavy path that u is on
    vector<int> in;       // dfs order in[u]
    vector<int> out;      // dfs order out[u] (exclusive)
    vector<int> rin;      // inverse of in[] (node at position)

    int curTime;

    explicit HLD(int n_=0) { init(n_); }

    // Optionally build directly from an adjacency list
    HLD(const vector<vector<int>>& adj, int root_=1) {
        init((int)adj.size() - 1);
        g = adj;
        build(root_);
    }

    void init(int n_) {
        n = n_;
        root = 1;
        g.assign(n + 1, {});
        parent.assign(n + 1, 0);
        depth.assign(n + 1, 0);
        heavy.assign(n + 1, -1);
        sz.assign(n + 1, 0);
        head.assign(n + 1, 0);
        in.assign(n + 1, 0);
        out.assign(n + 1, 0);
        rin.assign(n + 1, 0);
        curTime = 0;
    }

    void addEdge(int u, int v) {
        g[u].push_back(v);
        g[v].push_back(u);
    }

    void build(int root_=1) {
        root = root_;
        // 1) sizes, heavy child, parent, depth
        dfs1(root, 0);
        // 2) assign head & dfs order
        dfs2(root, root);
    }

    // LCA in O(log N)
    int lca(int u, int v) const {
        while (head[u] != head[v]) {
            if (depth[ head[u] ] < depth[ head[v] ]) swap(u, v);
            u = parent[ head[u] ];
        }
        return depth[u] < depth[v] ? u : v;
    }

    // Distance by depths + LCA
    int dist(int u, int v) const {
        int w = lca(u, v);
        return depth[u] + depth[v] - 2 * depth[w];
    }

    // Is u ancestor of v?
    bool isAncestor(int u, int v) const {
        return in[u] <= in[v] && out[v] <= out[u];
    }

    // (Optional) Jump k steps up from u. Requires binary lifting for O(logN).
    // Here is an O(logN * #chains) version using heads only; good enough for many uses:
    int jumpUp(int u, int k) const {
        // Move up whole heavy paths first.
        while (u && k > 0) {
            int h = head[u];
            int up = depth[u] - depth[h];
            if (k <= up) {
                // within the same heavy path: just move by index
                return rin[ in[u] - k ];
            }
            // jump to the parent of head and decrease k by the path height + 1 (for head itself)
            k -= (up + 1);
            u = parent[h];
        }
        return u == 0 ? -1 : u; // if k too large, return -1
    }

private:
    // First DFS: compute subtree sizes and heavy child
    void dfs1(int u, int p) {
        parent[u] = p;
        depth[u] = (p ? depth[p] + 1 : 0);
        sz[u] = 1;
        int maxSub = 0;

        for (int v : g[u]) if (v != p) {
            dfs1(v, u);
            sz[u] += sz[v];
            if (sz[v] > maxSub) {
                maxSub = sz[v];
                heavy[u] = v;
            }
        }
    }

    // Second DFS: decompose into heavy paths, assign head and in-order indices
    void dfs2(int u, int h) {
        head[u] = h;
        in[u] = ++curTime;
        rin[curTime] = u;

        if (heavy[u] != -1) {
            dfs2(heavy[u], h); // continue the heavy path
        }
        for (int v : g[u]) if (v != parent[u] && v != heavy[u]) {
            dfs2(v, v);       // start a new heavy path at v
        }
        out[u] = curTime + 1;
    }
};

/* ------------------------------
Example:

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    HLD hld(n);
    for (int i = 1; i <= n - 1; ++i) {
        int u, v; cin >> u >> v;
        hld.addEdge(u, v);
    }
    int root = 1;
    hld.build(root);

    int q; cin >> q;
    while (q--) {
        int u, v; cin >> u >> v;
        cout << hld.lca(u, v) << "\n";
    }
}
*/