//debugla!!!!
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
using namespace std;
const int lg=17;
int n,m;
vector<int>komsu[120023];
int bin[120023][lg];
int dep[120023];
vector<int>dir[120023*(lg+1)*2];
int vis[120023*(lg+1)*2];
pair<int,int>p[120023];
int lca(int a,int b){
if(dep[a]<dep[b])swap(a,b);
for(int i=0;i<lg;i++){
if(((dep[a]-dep[b])>>i)&1){
a=bin[a][i];
}
}
if(a==b)return a;
for(int i=lg-1;i>=0;i--){
if(bin[a][i]!=bin[b][i]){
a=bin[a][i];
b=bin[b][i];
}
}
return bin[a][0];
}
void dfs(int pos){
for(int i=1;i<lg;i++){
bin[pos][i]=bin[bin[pos][i-1]][i-1];
}
for(int x:komsu[pos]){
if(x==bin[pos][0])continue;
bin[x][0]=pos;
dep[x]=dep[pos]+1;
dfs(x);
}
}
bool dfs2(int pos){
if(pos>=n*(lg+1)*2)return true;
//cout<<pos<<" ";
vis[pos]=1;
for(int x:dir[pos]){
if(vis[x]==2)continue;
if(vis[x]==1){
cout<<x<<"*";
return false;
}
if(!dfs2(x)){
cout<<pos<<" ";
return false;
}
}
vis[pos]=2;
return true;
}
void code(){
cin>>n;
for(int i=0;i<n;i++){
komsu[i].clear();
}
for(int i=0;i<(lg+1)*n*2;i++){
dir[i].clear();
vis[i]=0;
}
for(int i=1;i<n;i++){
int x,y;cin>>x>>y;
x--;y--;
komsu[x].pb(y);
komsu[y].pb(x);
}
for(int i=0;i<lg;i++)
bin[n][i]=n;
bin[0][0]=n;
dep[n]=-1;
dep[0]=0;
dfs(0);
cin>>m;
for(int i=0;i<m;i++){
cin>>p[i].fr>>p[i].sc;
p[i].fr--;p[i].sc--;
int lc=lca(p[i].fr,p[i].sc);
int a=p[i].fr,b=p[i].sc;
int pos=bin[a][0];
dir[b*(lg+1)*2].pb(a*(lg+1)*2+1);
for(int j=lg-1;j>=0;j--){
if(dep[bin[pos][j]]>=dep[lc]){
dir[pos*(lg+1)*2+(j+1)*2+1].pb(a*(lg+1)*2+1);
pos=bin[bin[pos][j]][0];
}
}
if(pos==lc){
dir[pos*(lg+1)*2+1].pb(a*(lg+1)*2+1);
}
pos=b;
for(int j=lg-1;j>=0;j--){
if(dep[bin[pos][j]]>dep[lc]){
dir[pos*(lg+1)*2+(j+1)*2+1].pb(a*(lg+1)*2+1);
pos=bin[bin[pos][j]][0];
}
}
if(bin[pos][0]==lc){
dir[pos*(lg+1)*2+1].pb(a*(lg+1)*2+1);
}
swap(a,b);
pos=bin[a][0];
for(int j=lg-1;j>=0;j--){
if(dep[bin[pos][j]]>=dep[lc]){
dir[a*(lg+1)*2].pb(pos*(lg+1)*2+(j+1)*2);
pos=bin[bin[pos][j]][0];
}
}
if(pos==lc){
dir[a*(lg+1)*2].pb(pos*(lg+1)*2);
}
pos=b;
for(int j=lg-1;j>=0;j--){
if(dep[bin[pos][j]]>dep[lc]){
dir[a*(lg+1)*2].pb(pos*(lg+1)*2+(j+1)*2);
pos=bin[bin[pos][j]][0];
}
}
if(bin[pos][0]==lc&&pos!=lc){
dir[a*(lg+1)*2].pb(pos*(lg+1)*2);
}
}
for(int i=0;i<n*(lg+1)*2;i+=2){
int kat=(i>>1)%(lg+1);
if(kat==0)continue;
int x=(i>>1)/(lg+1);
if(kat!=1)x=bin[x][kat-2];
x=bin[x][0];
dir[i-1].pb(i+1);
dir[x*(lg+1)*2+(kat-1)*2+1].pb(i+1);
dir[i].pb(i-2);
dir[i].pb(x*(lg+1)*2+(kat-1)*2);
}
for(int i=0;i<n*(lg+1)*2;i++){
/*cout<<i<<": ";
for(int x:dir[i])cout<<x<<" ";
cout<<endl;
continue;*/
if(vis[i])continue;
if(!dfs2(i)){
cout<<"No";
return;
}
//cout<<endl;
}
cout<<"Yes";
}
int main(){
ios_base::sync_with_stdio(23-23);cin.tie(0);
int q;cin>>q;
while(q--){
code();cout<<endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |