#include<bits/stdc++.h> using namespace std; #define foru(i,a,b) for(int i=(a); i<=(b); ++i) #define ford(i,a,b) for(int i=(a); i>=(b); --i) #define rep(i,a) for(int i=0; i<(a); ++i) #define sz(a) (int)(a).size() #define all(a) (a).begin(),(a).end() #define bit(s,i) (((s)>>(i))&1) #define ii pair<int,int> #define vi vector<int> #define vii vector<ii> #define fi first #define se second #define ll long long #define eb emplace_back #define pb push_back #define __builtin_popcount __builtin_popcountll #define _ << " " << template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;} template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;} const int N=121212; int n,m,s[N],t[N]; vi adj[N]; void input(){ /// also reset here cin>>n; foru(i,1,n){ adj[i].clear(); } rep(i,n-1){ int u,v; cin>>u>>v; adj[u].eb(v); adj[v].eb(u); } cin>>m; foru(i,1,m){ cin>>s[i]>>t[i]; } } int sz[N],par[N]; void dfs(int u, int p=-1){ sz[u]=1; for(int v:adj[u]) if(v!=p){ par[v]=u; dfs(v,u); sz[u]+=sz[v]; } } int idCh[N],head[N],bigC[N],curCh=1; int tin[N],tout[N],tour[N],tim; void hld(int u, int p=-1){ if(!head[curCh]){ head[curCh]=u; } idCh[u]=curCh; tin[u]=++tim; tour[tim]=u; bigC[u]=-1; for(int v:adj[u]) if(v!=p) if(bigC[u]==-1 || sz[bigC[u]]<sz[v]) bigC[u]=v; if(bigC[u]!=-1) hld(bigC[u],u); for(int v:adj[u]) if(v!=p && v!=bigC[u]){ ++curCh; hld(v,u); } tout[u]=tim; } void buildTree(){ /// remember to reset dfs(1); foru(i,1,curCh) head[i]=0; curCh=1; tim=0; hld(1); } /// a -> b: a phai di truoc b /// int cur; int lc[5*N],rc[5*N]; int nod1[N],nod2[N],root1,root2; vi adj2[5*N]; void build1(int id, int l=1, int r=n){ // cout<<"1 "<<id _ l _ r <<'\n'; if(l==r){ nod1[l]=id; return; } int mid=(l+r)>>1; lc[id]=++cur; build1(lc[id],l,mid); rc[id]=++cur; build1(rc[id],mid+1,r); adj2[lc[id]].eb(id); adj2[rc[id]].eb(id); } void add1(int u, int v, int ops, int id, int l=1, int r=n){ // return; if(u>r||v<l) return; if(u<=l&&r<=v){ // cout<<id _ ops<<'\n'; adj2[id].eb(ops); return; } int mid=(l+r)>>1; add1(u,v,ops,lc[id],l,mid); add1(u,v,ops,rc[id],mid+1,r); } void build2(int id, int l=1, int r=n){ // cout<<"2 "<<id _ l _ r<<'\n'; if(l==r){ nod2[l]=id; return; } int mid=(l+r)>>1; lc[id]=++cur; build2(lc[id],l,mid); rc[id]=++cur; build2(rc[id],mid+1,r); adj2[id].eb(lc[id]); adj2[id].eb(rc[id]); } void add2(int u, int v, int ops, int id, int l=1, int r=n){ if(u>r||v<l) return; if(u<=l&&r<=v){ // cout<<ops _ id<<'\n'; adj2[ops].eb(id); return; } int mid=(l+r)>>1; add2(u,v,ops,lc[id],l,mid); add2(u,v,ops,rc[id],mid+1,r); } void buildEdge(){ foru(i,1,cur){ adj2[i].clear(); } // cout<<tour[3]<<'\n'; cur=m; root1=++cur; build1(root1); root2=++cur; build2(root2); foru(i,1,m){ /// s[i], t[i] adj2[i].eb(nod1[tin[s[i]]]); adj2[nod2[tin[t[i]]]].eb(i); int u=s[i], v=t[i]; add1(tin[v],tin[v],i,root1); add2(tin[u],tin[u],i,root2); if(tin[u]>tin[v]) swap(u,v); if(tout[v]<=tout[u]){ v=par[v]; while(idCh[u]!=idCh[v]){ int t=head[idCh[v]]; add1(tin[t],tin[v],i,root1); add2(tin[t],tin[v],i,root2); v=par[t]; } if(tin[u]+1<=tin[v]){ add1(tin[u]+1,tin[v],i,root1); add2(tin[u]+1,tin[v],i,root2); } } else{ u=par[u]; v=par[v]; while(idCh[u]!=idCh[v]){ if(idCh[u]>idCh[v]) swap(u,v); int t=head[idCh[v]]; add1(tin[t],tin[v],i,root1); add2(tin[t],tin[v],i,root2); v=par[t]; } if(tin[u]>tin[v]) swap(u,v); add1(tin[u],tin[v],i,root1); add2(tin[u],tin[v],i,root2); } } } int vis[5*N]; bool isCycle; void dfs2(int u){ vis[u]=1; for(int v:adj2[u]){ if(vis[v]==1) isCycle=1; if(!vis[v]) dfs2(v); } vis[u]=2; } void searchGraph(){ isCycle=0; foru(i,1,cur) vis[i]=0; foru(i,1,cur) if(!vis[i]) dfs2(i); } void solve(){ input(); buildTree(); buildEdge(); searchGraph(); cout<<(isCycle?"No":"Yes")<<'\n'; } int32_t main(){ #define task "test" if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } cin.tie(0)->sync_with_stdio(0); int tc=1; cin>>tc; foru(i,1,tc){ solve(); } }

jail.cpp: In function 'int32_t main()':
jail.cpp:222:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  222 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jail.cpp:223:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  223 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~