#include <iostream> #include <bits/stdc++.h> using namespace std; const int N=120001; struct arbore { long long scor,lz; }aint[4*N]; int n,binlift[N][17],height[N],sub[N],top[N]; int get_lca(int a,int b) { if (height[a]<height[b]) swap(a,b); for (int i=16;i>=0;i--) { if (height[binlift[a][i]]>=height[b]) a=binlift[a][i]; } if (a==b) return a; for (int i=16;i>=0;i--) { if (binlift[a][i]!=binlift[b][i]) { a=binlift[a][i]; b=binlift[b][i]; } } return binlift[a][0]; } vector<int>adj[N]; void propaga(int nod) { if (aint[nod].lz==0) return; aint[nod*2].scor += aint[nod].lz; aint[nod*2+1].scor += aint[nod].lz; aint[nod*2].lz += aint[nod].lz; aint[nod*2+1].lz += aint[nod].lz; aint[nod].lz = 0; } void update(int nod,int st,int dr,int l,int r,int val) { if (l<=st && dr<=r) { aint[nod].scor+=val; aint[nod].lz+=val; return ; } else if (l>dr || st>r) { return; } propaga(nod); int mij = (st+dr)/2; update(nod*2, st, mij, l ,r, val); update(nod*2+1 ,mij+1, dr , l , r , val); aint[nod].scor=min(aint[nod*2].scor, aint[nod*2+1].scor); } int query(int nod, int st, int dr) { if (st==dr) return st; int mij=(st+dr)/2; if (aint[nod*2].scor==1) return query(nod*2,st,mij); else return query(nod*2+1,mij+1,dr); } void reset() { for (int i=1;i<=n;i++) adj[i].clear(); } void dfs(int nod,int p) { height[nod]=height[p]+1; binlift[nod][0]=p; sub[nod]=1; for (int i=1;i<=16;i++) { binlift[nod][i]=binlift[binlift[nod][i-1]][i-1]; } for (auto u:adj[nod]) { if (u!=p) { dfs(u,nod); sub[nod]+=sub[u]; } } } int euler[N],where[N],global; void dfs_hld(int nod,int p,int lant) { global++; euler[global]=nod; where[nod]=global; top[nod]=lant; int maxx=-1,go=-1; for (auto u:adj[nod]) { if (u!=p) { if (sub[u]>maxx) { maxx=sub[u]; go=u; } } } if (go!=-1) { dfs_hld(go,nod,lant); } for (auto u:adj[nod]) { if (u!=p && u != go) { dfs_hld(u,nod,u); } } } int start[N]; void updateaza(int start,int end,int val) { int op=20000; while (height[start]>=height[end]) { int nod=top[start]; if (height[top[start]]<height[end]) nod=end; //cout<<start<<" "<<nod<<" "<<"huh"<<'\n'; int interval=where[start]; int interval_end=where[nod]; op--; assert(op>=5); //cout<<interval<<" "<<interval_end<<'\n'; assert(interval_end<=interval); update(1,1,n,interval_end,interval,val); start=binlift[nod][0]; //cout<<start<<" "<<nod<<'\n'; } } void split(int a,int b,int scor) { int x=get_lca(a,b); //cout<<a<<" "<<b<<" "<<x<<'\n'; updateaza(a,x,scor); //return; int t=b; for (int i=16;i>=0;i--) { if (height[binlift[t][i]]>height[x]) t=binlift[t][i]; } if (b!=x) updateaza(b,t,scor); } void solve() { cin>>n; for (int i=1;i<n;i++) { int x,y; cin>>x>>y; adj[x].push_back(y); adj[y].push_back(x); } dfs(1,0); dfs_hld(1,0,1); for (int i=1;i<=n;i++) { update(1,1,n,i,i,1e9); } int m; cin>>m; for (int i=1;i<=m;i++) { int x,y; cin>>x>>y; start[x]=y; update(1,1,n,where[x],where[x],-1e9); } int cat_scade=m; for (int i=1;i<=n;i++) { if (start[i]) { int a=i; int b=start[i];; //cout<<a<<" "<<b<<'\n'; split(a,b,1); } } //return ; //cout<<aint[1].scor<<'\n'; int val=1; while (val==1) { val=aint[1].scor; //cout<<val<<" "<<"huh"<<endl; //cout<<val<<'\n'; if (val==1) { int a=query(1,1,n); cat_scade--; update(1,1,n,a,a,1e9); int b=start[a]; //cout<<a<<" "<<b<<'\n'; split(a,b,-1); if (cat_scade==0) break; } } if (cat_scade==0) { cout<<"Yes"<<'\n'; } else cout<<"No"<<'\n'; for (int i=1;i<=n;i++) { start[i]=0; adj[i].clear(); top[i]=0; } for (int i=1;i<=4*n;i++) { aint[i].lz=0; aint[i].scor=0; } global=0; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int test; cin>>test; while (test--) solve(); return 0; }