/// testing with m<=6 #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; const int LG=17; int n,m,s[N],t[N]; bool dp[1<<6]; int tin[N],tout[N],up[N][LG+1],h[N],tim; vi adj[N]; void dfs(int u, int p=-1){ tin[u]=++tim; for(int v:adj[u]) if(v!=p){ up[v][0]=u; foru(i,1,LG) up[v][i]=up[up[v][i-1]][i-1]; h[v]=h[u]+1; dfs(v,u); } tout[u]=tim; } int lca(int u, int v){ if(h[u]<h[v]) swap(u,v); int df=h[u]-h[v]; foru(i,0,LG) if(bit(df,i)) u=up[u][i]; if(u==v) return u; ford(i,LG,0) if(up[u][i]!=up[v][i]) u=up[u][i], v=up[v][i]; return up[u][0]; } int f[N]; void upd(int id, int val){ for(; id<=n; id+=id&-id) f[id]+=val; } void upd(int l, int r, int val){ upd(l,val); upd(r+1,-val); } int get(int id){ int res=0; for(; id>0; id-=id&-id) res+=f[id]; return res; } void solve(){ cin>>n; foru(i,1,n) adj[i].clear(); rep(i,n-1){ int a,b; cin>>a>>b; adj[a].eb(b); adj[b].eb(a); } cin>>m; foru(i,1,m) cin>>s[i]>>t[i]; tim=0; dfs(1); rep(msk,1<<m) dp[msk]=0; dp[0]=1; rep(msk,1<<m) if(dp[msk]){ foru(i,1,m){ if(bit(msk,i-1)){ upd(tin[t[i]],tout[t[i]],1); } else{ upd(tin[s[i]],tout[s[i]],1); } } foru(i,1,m){ if(!bit(msk,i-1)){ upd(tin[s[i]],tout[s[i]],-1); int hihi=get(tin[s[i]])+get(tin[t[i]])-2*get(tin[up[lca(s[i],t[i])][0]]); if(hihi==0) dp[msk|(1<<(i-1))]=1; upd(tin[s[i]],tout[s[i]],1); } } foru(i,1,m){ if(bit(msk,i-1)){ upd(tin[t[i]],tout[t[i]],-1); } else{ upd(tin[s[i]],tout[s[i]],-1); } } } cout<<(dp[(1<<m)-1]?"Yes\n":"No\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:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jail.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~