#include #include #include #define LL long long #define Re register int using namespace std; const int N=1e6+5,logN=14; int o,n,m,x,y,t,T,dfn_O,A[N],Q[N],dfn[N],idx[N],Ans[N],cnt[N],son[N],deep[N],size[N],head[N]; struct QAQ{int to,next;}a[N]; inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;} struct Query{ int o,head[N]; struct QAQ{int to,id,next;}a[N]; inline void add(Re x,Re y,Re id){a[++o].to=y,a[o].id=id,a[o].next=head[x],head[x]=o;} }QT; inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } struct LCA{ int ant[N][15]; inline void dfs(Re x,Re fa){ deep[x]=deep[ant[x][0]=fa]+1; for(Re i=1;(1<=0;--i) if((1<>1; sakura(L,mid),sakura(mid+1,R); Re p=mid;CL(); for(Re i=mid,j;i>=L&&(j=i+size[idx[i]]-1)<=R;--i){ insert(idx[i]); if(j<=mid)continue; while(p