#include <bits/stdc++.h>
using namespace std;
long long q,n,m;
vector<long long> f[100000001];
void read()
{
cin>>n;
for(long long i=1; i<=n; i++)
f[i].clear();
for(long long i=1; i<n; i++)
{
long long x,y;
cin>>x>>y;
f[x].push_back(y);
f[y].push_back(x);
}
}
long long num;
long long ts[100000001];// number of the vertex corresponding
long long te[100000001];// to the given tree and segment of the hld
long long dw[100000001];
long long up[100000001];
vector<long long> v[100000001],o[100000001];
void make_tree(long long i,long long l,long long r)
{
if(l==r)
{
ts[i]=num++;
dw[l]=ts[i];
te[i]=num++;
up[l]=te[i];
//cout<<l<<" "<<r<<" "<<te[i]<<endl;
return;
}
long long mid=(l+r)/2;
ts[i]=num++;
te[i]=num++;
//cout<<l<<" "<<r<<" "<<te[i]<<endl;
make_tree(i*2,l,mid);
make_tree(i*2+1,mid+1,r);
long long il=ts[i*2];
long long ir=ts[i*2+1];
v[ts[i]].push_back(il);
v[ts[i]].push_back(ir);
o[il].push_back(ts[i]);
o[ir].push_back(ts[i]);
il=te[i*2];
ir=te[i*2+1];
v[il].push_back(te[i]);
v[ir].push_back(te[i]);
o[te[i]].push_back(il);
o[te[i]].push_back(ir);
}
long long used[100000001];
long long jump[1000001][21];
long long sz[100000001];
long long pos[100000001];// new number of vertex i in original graph
long long chain[100000001];// leader of the chain in which i is
long long maxx[100000001];
long long lvl[100000001];
void necessities(long long i,long long h)
{
sz[i]=1;
used[i]=1;
for(long long j=0; j<f[i].size(); j++)
{
long long nb=f[i][j];
if(!used[nb])
{
necessities(nb,h+1);
sz[i]+=sz[nb];
if(sz[maxx[i]]<sz[nb])maxx[i]=nb;
}
}
}
long long cnt=1;
void hld(long long i,long long lead,int h)
{
pos[i]=cnt++;
chain[pos[i]]=pos[lead];
lvl[pos[i]]=h;
if(maxx[i])
{
hld(maxx[i],lead,h+1);
jump[pos[maxx[i]]][0]=pos[i];
}
for(long long j=0; j<f[i].size(); j++)
{
long long nb=f[i][j];
if(pos[nb]==0)
{
hld(nb,nb,h+1);
jump[pos[nb]][0]=pos[i];
}
}
}
void prec()
{
for(long long j=1; j<=20; j++)
{
for(long long i=1; i<=n; i++)
{
jump[i][j]=jump[jump[i][j-1]][j-1];
//cout<<i<<" "<<j<<" "<<jump[i][j]<<endl;
}
}
}
long long make_jump(long long x,long long k)
{
for(long long i=20; i>=0; i--)
if(k&(1<<i))
x=jump[x][i];
return x;
}
long long lca(long long x,long long y)
{
if(lvl[x]>lvl[y])swap(x,y);
y=make_jump(y,abs(lvl[y]-lvl[x]));
//cout<<x<<" "<<y<<endl;
if(x==y)return x;
for(long long i=20; i>=0; i--)
{
if(jump[x][i]!=jump[y][i])
{
x=jump[x][i];
y=jump[y][i];
}
}
return jump[x][0];
}
void update(long long i,long long l,long long r,long long ql,long long qr,long long pr)
{
if(ql>qr)return;
if(ql<=l&&r<=qr)
{
//cout<<l<<"-"<<r<<endl;
long long idx=ts[i];
//cout<<idx<<endl;
v[pr].push_back(idx);
o[idx].push_back(pr);
idx=te[i];
//cout<<idx<<endl;
v[idx].push_back(pr);
o[pr].push_back(idx);
return;
}
long long mid=(l+r)/2;
update(i*2,l,mid,ql,min(mid,qr),pr);
update(i*2+1,mid+1,r,max(ql,mid+1),qr,pr);
}
void make_graph()
{
/*for(int i=1;i<=n;i++)
cout<<chain[i]<<" ";
cout<<endl;*/
for(long long i=1; i<=m; i++)
{
long long x,y;
cin>>x>>y;
x=pos[x];
y=pos[y];
//cout<<i<<" "<<dw[pos[x]]<<" "<<up[pos[y]]<<endl;
v[dw[x]].push_back(i);
o[i].push_back(dw[x]);
v[i].push_back(up[y]);
o[up[y]].push_back(i);
long long ver=lca(x,y);
//cout<<ver<<endl;
long long c1=x;
while(1)
{
long long c2=chain[c1];
if(lvl[c2]<lvl[ver])c2=ver;
update(1,1,n,c2,c1,i);
//cout<<c2<<" "<<c1<<endl;
if(c2==ver)break;
c1=jump[c2][0];
}
c1=y;
while(1)
{
long long c2=chain[c1];
if(lvl[c2]<lvl[ver])c2=ver;
update(1,1,n,c2,c1,i);
//cout<<c2<<" "<<c1<<endl;
if(c2==ver)break;
c1=jump[c2][0];
}
}
}
long long used1[100000001];
stack<long long> st;
void dfs1(long long i)
{
used1[i]=1;
for(long long j=0; j<v[i].size(); j++)
{
long long nb=v[i][j];
if(!used1[nb])
{
dfs1(nb);
}
}
st.push(i);
}
long long used2[100000001];
void dfs2(long long i)
{
used2[i]=1;
for(long long j=0; j<o[i].size(); j++)
{
long long nb=o[i][j];
if(!used2[nb])
{
dfs2(nb);
}
}
}
void check()
{
memset(used1,0,sizeof(used1));
memset(used2,0,sizeof(used2));
for(long long i=1;i<=m;i++)
{
if(!used1[i])dfs1(i);
}
long long cnt=0;
while(st.size())
{
long long vr=st.top();
st.pop();
if(vr<=m&&!used2[vr])
{
cnt++;
dfs2(vr);
}
}
if(cnt==m)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>q;
while(q--)
{
for(long long i=1; i<=num; i++)
{
o[i].clear();
v[i].clear();
}
memset(maxx,0,sizeof(maxx));
memset(used,0,sizeof(used));
read();
cnt=1;
necessities(1,1);
hld(1,1,1);
prec();
cin>>m;
num=m+1;
make_tree(1,1,n);
make_graph();
/*for(long long i=1;i<num;i++)
{
cout<<i<<": ";
for(long long j=0;j<v[i].size();j++)
cout<<v[i][j]<<" ";
cout<<endl;
}*/
check();
}
return 0;
}
/*
1
8
1 7
1 8
8 3
3 2
7 6
7 5
5 4
*/
Compilation message
jail.cpp: In function 'void necessities(long long int, long long int)':
jail.cpp:69:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(long long j=0; j<f[i].size(); j++)
| ~^~~~~~~~~~~~
jail.cpp: In function 'void hld(long long int, long long int, int)':
jail.cpp:91:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(long long j=0; j<f[i].size(); j++)
| ~^~~~~~~~~~~~
jail.cpp: In function 'void dfs1(long long int)':
jail.cpp:200:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
200 | for(long long j=0; j<v[i].size(); j++)
| ~^~~~~~~~~~~~
jail.cpp: In function 'void dfs2(long long int)':
jail.cpp:214:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
214 | for(long long j=0; j<o[i].size(); j++)
| ~^~~~~~~~~~~~
/tmp/ccLX0HAg.o: in function `__tcf_2':
jail.cpp:(.text+0xd): relocation truncated to fit: R_X86_64_PC32 against symbol `o' defined in .bss section in /tmp/ccLX0HAg.o
/tmp/ccLX0HAg.o: in function `__tcf_0':
jail.cpp:(.text+0x5d): relocation truncated to fit: R_X86_64_PC32 against symbol `f' defined in .bss section in /tmp/ccLX0HAg.o
/tmp/ccLX0HAg.o: in function `__tcf_1':
jail.cpp:(.text+0xad): relocation truncated to fit: R_X86_64_PC32 against symbol `v' defined in .bss section in /tmp/ccLX0HAg.o
/tmp/ccLX0HAg.o: in function `necessities(long long, long long)':
jail.cpp:(.text+0xfd): relocation truncated to fit: R_X86_64_PC32 against symbol `f' defined in .bss section in /tmp/ccLX0HAg.o
jail.cpp:(.text+0x106): relocation truncated to fit: R_X86_64_PC32 against symbol `used' defined in .bss section in /tmp/ccLX0HAg.o
jail.cpp:(.text+0x10d): relocation truncated to fit: R_X86_64_PC32 against symbol `sz' defined in .bss section in /tmp/ccLX0HAg.o
jail.cpp:(.text+0x186): relocation truncated to fit: R_X86_64_PC32 against symbol `maxx' defined in .bss section in /tmp/ccLX0HAg.o
jail.cpp:(.text+0x19d): relocation truncated to fit: R_X86_64_PC32 against symbol `used' defined in .bss section in /tmp/ccLX0HAg.o
/tmp/ccLX0HAg.o: in function `hld(long long, long long, int)':
jail.cpp:(.text+0x1be): relocation truncated to fit: R_X86_64_PC32 against symbol `pos' defined in .bss section in /tmp/ccLX0HAg.o
jail.cpp:(.text+0x1ce): relocation truncated to fit: R_X86_64_PC32 against symbol `maxx' defined in .bss section in /tmp/ccLX0HAg.o
jail.cpp:(.text+0x1f7): additional relocation overflows omitted from the output
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
