#include <bits/stdc++.h>
using namespace std;
unordered_set<int>snodes;
unordered_set<int>tnodes;
unordered_set<int>sfin;
unordered_set<int>tfin;
void dfs(int st, vector<int>g[], int p, int t, int revs[], int revt[]){
snodes.insert(revs[st]);
tnodes.insert(revt[st]);
if(st==t){
for(int i : snodes){
sfin.insert(i);
}
for(int i : tnodes){
tfin.insert(i);
}
snodes.erase(revs[st]);
tnodes.erase(revt[st]);
return;
}
for(int i : g[st]){
if(i==p)
continue;
if(sfin.size())
break;
dfs(i,g,st,t,revs,revt);
}
snodes.erase(revs[st]);
tnodes.erase(revt[st]);
}
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];
sfin.clear();
tfin.clear();
for(int i = 0;i<m;i++){
dfs(s[i],g,-1,t[i],revs,revt);
for(int j : sfin){
spath[i].insert(j);
}
for(int j : tfin){
tpath[i].insert(j);
}
sfin.clear();
tfin.clear();
}
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... |