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;
}