struct LCA
{
	static const int N = 5e5+5,M = 1e6+5,P = 20;
	struct node {int to,ne;} edge[M];
	int head[N],len = 0,dep[N],fa[N][P];
	struct iterator
	{
		int indx;LCA *g;
		iterator (int _i,LCA *_g) : indx(_i) , g(_g) {}
		iterator operator++(int) {iterator t = *this;return indx = g->edge[indx].ne,t;}
		int operator*() {return g->edge[indx].to;}
		operator bool () {return (bool)indx;}
	};
	void insert(int u,int v) {edge[++len] = {v,head[u]},head[u] = len;}
	void add(int u,int v) {insert(u,v),insert(v,u);}
	iterator begin(int x) {return iterator(head[x],this);}
	void dfs(int x = 1,int f = 0)
	{
		dep[x] = dep[f]+1,fa[x][0] = f;
		for (int i = 1;i < P;i ++) fa[x][i] = fa[fa[x][i-1]][i-1];
		for (auto i = begin(x);i;i ++) if (*i != f) dfs(*i,x);
	}
	int lca(int x,int y)
	{
		if (dep[x] < dep[y]) swap(x,y);
		for (int i = P-1;i >= 0;i --) if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
		if (x == y) return x;
		for (int i = P-1;i >= 0;i --) if (fa[x][i] != fa[y][i]) x = fa[x][i],y = fa[y][i];
		return fa[x][0];
	}
};