#include using namespace std; inline int rd() { int m=0,s=0;char ch=getchar(); while(!isdigit(ch)) m|=(ch=='-'),ch=getchar(); while( isdigit(ch)) s=s*10+ch-'0',ch=getchar(); return m?-s:s; } bool MBE; namespace SOLVER { int n,in[500005],tim,dep[500005],st[20][500005],st2[20][500005];vector g[500005]; void dfs(int u,int p) { in[u]=++tim;dep[u]=dep[p]+1;st[0][in[u]]=p; for(int v:g[u]) if(v!=p) dfs(v,u); } inline int cmp(int x,int y) {return dep[x]in[y]) swap(x,y); int k=__lg(in[y]-in[x]);return cmp(st[k][in[x]+1],st[k][in[y]-(1< a,b,c;} t[(1<<20)+5]; #define ls (p<<1) #define rs (p<<1|1) void build(int p,int l,int r) { t[p].a.resize(r-l+3),t[p].b.resize(r-l+3),t[p].c.resize(r-l+3); if(l==r) {t[p].a[1]=dep[l];return;} int mid=(l+r)>>1;build(ls,l,mid),build(rs,mid+1,r); t[p].b[mid-l]=mid,t[p].b[mid+1-l]=mid+1; for(int i=mid-1;i>=l;i--) t[p].b[i-l]=lca(i,t[p].b[i+1-l]); for(int i=mid+2;i<=r;i++) t[p].b[i-l]=lca(i,t[p].b[i-1-l]); for(int i=2,pos=mid+1;i<=r-l+1;i++) { if(i<=mid-l+1) t[p].a[i]=max(t[p].a[i],t[ls].a[i]); if(i<=r-mid) t[p].a[i]=max(t[p].a[i],t[rs].a[i]); while(pos<=mid||pos-i+1=dep[t[p].b[pos-i+1-l]]) pos++; t[p].c[i]=pos; for(int j=pos-1;j<=pos;j++) if(j>mid&&j<=r&&j-i+1<=mid&&j-i+1>=l) t[p].a[i]=max(t[p].a[i],dep[lca(t[p].b[j-l],t[p].b[j-i+1-l])]); } t[p].a[1]=max(t[ls].a[1],t[rs].a[1]); } int query(int p,int l,int r,int L,int R,int k) { if(r-l+1r) return 0;if(L<=l&&r<=R) return t[p].a[k]; int mid=(l+r)>>1,ans=0; if(k!=1&&L<=mid&&R>mid) { int pos=t[p].c[k],ll=max(L+k-1,mid+1),rr=min(mid+k-1,R); if(pos>rr) pos=rr;if(posmid&&i<=R&&i-k+1<=mid&&i-k+1>=L) ans=max(ans,dep[lca(t[p].b[i-l],t[p].b[i-k+1-l])]); } if(L<=mid) ans=max(ans,query(ls,l,mid,L,min(R,mid),k)); if(R>mid) ans=max(ans,query(rs,mid+1,r,max(L,mid+1),R,k)); return ans; } void MAIN() { cin>>n;for(int i=1,u,v;i