//LCA//树链剖分 在线 #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int n,m,root,cnt,head[500001];int hvyson[500001],fa[500001],siz[500001],dep[500001],top[500001];struct uio{ int to,next;}edge[1000001];void add(int x,int y){ edge[++cnt].next=head[x]; edge[cnt].to=y; head[x]=cnt;}void dfs1(int x,int f,int depth){ dep[x]=depth; fa[x]=f; siz[x]=1; int maxson=-1; for(int i=head[x];i;i=edge[i].next) { int y=edge[i].to; if(y==f) continue; dfs1(y,x,depth+1); siz[x]+=siz[y]; if(siz[y]>maxson) { hvyson[x]=y; maxson=siz[y]; } }}void dfs2(int x,int topf){ top[x]=topf; if(!hvyson[x]) return; dfs2(hvyson[x],topf); for(int i=head[x];i;i=edge[i].next) { int y=edge[i].to; if(y==fa[x]||y==hvyson[x]) continue; dfs2(y,y); }}int lca(int x,int y){ while(top[x]!=top[y]) { if(dep[top[x]]