// ARC048 D をコピペ #include using namespace std; typedef long long ll; typedef vector vi; typedef vector vl; typedef complex P; typedef pair pii; #define REP(i,n) for(ll i=0;iz&&x!=z) || (x>y&&y Q; depth[0] = 0; Q.push(0); while(!Q.empty()){ int pos = Q.front(); Q.pop(); int d = depth[pos]; REP(i,g[pos].size()){ int to = g[pos][i]; if(depth[to]!=INF)continue; depth[to] = d+1; Q.push(to); // ダブリング準備 anc[to][0] = pos; query[to][0] = (d+1<2?0:kado(to,pos,anc[pos][0])); int id = 1; int cur = pos; while(anc[cur][id-1]!=INF){ int next = anc[cur][id-1]; anc[to][id] = next; query[to][id] = query[to][id-1] & query[cur][id-1]; cur = next; ++id; } } } int q; scanf("%d",&q); while(q--){ int s,t; scanf("%d%d",&s,&t); --s; --t; if(depth[s]>depth[t])swap(s,t); int x=s, y=t; int diff = depth[y]-depth[x]; REP(k,20){ if(diff&1) y = anc[y][k]; diff>>=1; } REP(_k,20){ int k = 20-1-_k; if(anc[x][k]!=INF && anc[x][k]!=anc[y][k]){ x = anc[x][k]; y = anc[y][k]; } } bool flag = true; if(x!=y){ // s --- x - lca - y --- t int lca = anc[x][0]; flag &= kado(x,lca,y); flag &= kado(anc[s][0],s,t); flag &= kado(anc[t][0],t,s); diff = max(0,depth[s]-depth[lca]-1); x = s; REP(k,20){ if(diff&1){ flag &= query[x][k]; x = anc[x][k]; } diff >>= 1; } diff = max(0,depth[t]-depth[lca]-1); x = t; REP(k,20){ if(diff&1){ flag &= query[x][k]; x = anc[x][k]; } diff >>= 1; } }else{ // s=x=lca=y --- t diff = max(0,depth[t]-depth[s]-1); x = t; REP(k,20){ if(diff&1){ flag &= query[x][k]; x = anc[x][k]; } diff >>= 1; } flag &= kado(x,s,t); flag &= kado(s,t,anc[t][0]); } if(flag)puts("YES"); else puts("NO"); } return 0; }