#include <bits/stdc++.h>
using namespace std;
unordered_set<int>sfin;
unordered_set<int>tfin;
void dfs(int st, vector<int>g[], int p, int d, int dep[], int par[]){
par[st]=p;
dep[st]=d;
for(int i : g[st]){
if(i==p)
continue;
dfs(i,g,st,d+1,dep,par);
}
}
void finder(int s, int t, int revs[], int revt[], int dep[], int par[]){
sfin.clear();
tfin.clear();
while(s!=t){
if(dep[s]<dep[t]){
swap(s,t);
}
//s is deeper now
sfin.insert(revs[s]);
tfin.insert(revt[s]);
s=par[s];
}
sfin.insert(revs[s]);
tfin.insert(revt[s]);
}
bool cyc;
void checkcyc(int st, vector<int>g[], int vis[]){
vis[st]=1;
for(int i : g[st]){
if(vis[i]==1){
cyc=1;
}
if(vis[i])
continue;
checkcyc(i,g,vis);
}
vis[st]=2;
}
void solve(){
int n;
cin >> n;
vector<int>g[n];
for(int i = 0;i<n-1;i++){
int a,b;
cin >> a >> b;
a--;b--;
g[a].push_back(b);
g[b].push_back(a);
}
int m;
cin >> m;
int s[m],t[m];
int revs[n],revt[n];
fill(revs,revs+n,-1);
fill(revt,revt+n,-1);
for(int i = 0;i<m;i++){
cin >> s[i] >> t[i];
s[i]--;
t[i]--;
revs[s[i]]=i;
revt[t[i]]=i;
}
unordered_set<int>spath[m];
unordered_set<int>tpath[m];
int dep[n];
int par[n];
dfs(0,g,-1,0,dep,par);
for(int i = 0;i<m;i++){
finder(s[i],t[i],revs,revt,dep,par);
for(int j : sfin){
spath[i].insert(j);
}
for(int j : tfin){
tpath[i].insert(j);
}
}
vector<int>g2[m];
for(int i = 0;i<m;i++){
for(int j : spath[i]){
if(j==-1||j==i){
continue;
}
g2[j].push_back(i);
}
for(int j : tpath[i]){
if(j==-1||j==i){
continue;
}
g2[i].push_back(j);
}
}
//now check for cycle.
cyc=0;
int vis[m];
fill(vis,vis+m,0);
for(int i = 0;i<m;i++){
if(vis[i]==0){
checkcyc(i,g2,vis);
}
}
for(bool i : vis){
if(!i){
cyc=1;
}
}
if(cyc){
cout << "No\n";
}
else{
cout << "Yes\n";
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}
# | 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... |