#include using namespace std; using Int = long long; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a > G,par,lad; vector dep,nxt,len,pth,ord,hs; LevelAncestor(){} LevelAncestor(int n): n(n),G(n),dep(n),nxt(n,-1),len(n),pth(n),ord(n),hs(n+1,0){ h=1; while((1<(n,-1)); for(int i=2;i<=n;i++) hs[i]=hs[i>>1]+1; } void add_edge(int u,int v){ G[u].emplace_back(v); G[v].emplace_back(u); } void dfs(int v,int p,int d,int f){ if(nxt[v]<0){ par[0][nxt[v]=v]=p; len[v]=dep[v]=d; for(int u:G[v]){ if(u==p) continue; dfs(u,v,d+1,0); if(len[v]dep[v]) swap(u,v); for(int k=0;k>k&1){ v=par[k][v]; } } if(u==v) return u; for(int k=h-1;k>=0;k--){ if(par[k][u]!=par[k][v]){ u=par[k][u]; v=par[k][v]; } } return par[0][u]; } int up(int v,int d){ if(d==0) return v; v=par[hs[d]][v]; d-=1LL<>n; vector a(n); for(int i=0;i>a[i]; LevelAncestor la(n); for(int i=1;i>x>>y; x--;y--; la.add_edge(x,y); } la.build(); auto par=la.par; auto dep=la.dep; auto is_kado=[&](int x,int y,int z)->int{ if(x==y||x==z||y==z) return 0; return (xz)||(x>y&&yint{ if(dep[v]<2) return 0; return is_kado(a[v],a[par[0][v]],a[par[1][v]]); }; int h=la.h; vector > dp(h,vector(n,0)); for(int j=0;j>q; for(int i=0;i>x>>y; x--;y--; if(la.distance(x,y)<=2){ cout<<"NO\n"; continue; } if(dep[x]>dep[y]) swap(x,y); int z=la.lca(x,y); int flg=1; if(x==z){ int cx=la.up(y,la.distance(y,z)-1); int py=par[0][y]; flg&=is_kado(a[cx],a[x],a[y]); flg&=is_kado(a[x],a[y],a[py]); }else{ int px=par[0][x]; int py=par[0][y]; flg&=is_kado(a[x],a[y],a[py]); flg&=is_kado(a[px],a[x],a[y]); int lx=la.up(x,la.distance(x,z)-1); int ly=la.up(y,la.distance(y,z)-1); flg&=is_kado(a[lx],a[z],a[ly]); } for(int w:{x,y}){ int v=w,d=dep[w]-dep[z]-1,k=0; while(d>0){ if(d&1){ flg&=dp[k][v]; v=par[k][v]; } k++; d>>=1; } } cout<<(flg?"YES\n":"NO\n"); } cout<