#include <bits/stdc++.h>
using namespace std;
#define ii pair <int, int>
#define ff first
#define ss second
#define bit(i) (1 << (i))
#define fto(i, a, b) for (int i = (a); i <= (b); ++i)
#define fdto(i, a, b) for (int i = (a); i >= (b); --i)
#define flto(i, a, b) for (int i = (a); (1 << i) <= (b); ++i)
#define pb push_back
#define pf push_front
#define endl "\n"
#define oo (int)(1e9 + 7)
#define maxN 120005
#define l(s) s.length()
#define vi vector <int>
#define vii vector <ii>
#define fat(x, y) for (auto x : y)
#define fit(x, y) for (int x : y)
#define fiit(x, y) for (ii x : y)
#define EPS 1e-9
#define pi (acos(-1))
#define ll long long
int n, m, tme, ok;
vi ke[maxN], tp[maxN], adj[maxN], topo;
int s[maxN], t[maxN];
int par[maxN], h[maxN];
int p[maxN], vst[maxN];
int bt[maxN];
int pos[maxN], pot[maxN];
void pre_dfs(int u) {
for (int v : ke[u]) if (v != par[u]) {
par[v] = u;
h[v] = h[u] + 1;
pre_dfs(v);
}
}
int fSet(int u) {
return p[u] == 0 ? u : p[u] = fSet(p[u]);
}
void uSet(int u, int v) {
u = fSet(u);
v = fSet(v);
if (u == v) return;
p[v] = u;
}
void dfs(int u, int id) {
vst[u] = id;
//cout << pre << " " << u << endl;
int a = fSet(s[u]), b = fSet(t[u]);
vi kdg;
while (a != b) {
if (h[a] < h[b]) swap(a, b);
//vst[u] = 1;
if (pos[a] != 0 && pos[a] != u && !vst[pos[a]]) dfs(pos[a], id);
if (pot[a] != 0 && pot[a] != u && vst[pot[a]]) {
//cout << vst[pot[a]] << " " << id << endl;
//cout << pot[a] << " " << u << endl;
if (vst[pot[a]] == id) ok = ok;
else adj[vst[pot[a]]].pb(id);
}
//vst[u] = 1;
if (pos[par[a]] != 0 && pos[par[a]] != u && !vst[pos[par[a]]]) dfs(pos[par[a]], id);
if (pot[par[a]] != 0 && pot[par[a]] != u && vst[pot[par[a]]] && vst[pot[par[a]]] != vst[pot[a]]) {
if (vst[pot[par[a]]] == id) ok = ok;
else adj[vst[pot[par[a]]]].pb(id);
}
uSet(par[a], a);
a = fSet(a);
}
//for (int v : kdg) vst[v] = 0;
//vst[u] = 1;
tp[id].pb(u);
}
void dfs2(int u) {
bt[u] = 1;
for (int v : adj[u]) if (!bt[v]) dfs2(v);
for (int x : tp[u]) topo.pb(x);
}
void solve() {
cin >> n;
fto(i, 1, n) ke[i].clear(), adj[i].clear(), tp[i].clear(), pos[i] = 0, pot[i] = 0, p[i] = 0, par[i] = 0, h[i] = 0;
topo.clear();
fto(i, 1, n-1) {
int u, v; cin >> u >> v;
ke[u].pb(v);
ke[v].pb(u);
}
tme = 0;
pre_dfs(1);
cin >> m;
fto(i, 1, m) {
cin >> s[i] >> t[i];
pos[s[i]] = i;
pot[t[i]] = i;
vst[i] = 0;
bt[i] = 0;
if (s[i] == t[i]) {
topo.pb(i);
vst[i] = 1;
}
}
ok = 1; tme = 0;
fto(i, 1, m) if (!vst[i]) dfs(i, ++tme);
if (!ok) {
cout << "No" << endl;
return;
}
//cout << tme << endl;
fto(i, 1, tme) if (!bt[i]) dfs2(i);
fto(i, 1, n) p[i] = 0;
fto(i, 1, m) vst[i] = 1;
for (int u : topo) {
vst[u] = u;
//cout << u << " ";
}
//cout << endl;
for (int u : topo) {
//cout << u << endl;
vst[u] = 0;
int a = fSet(s[u]), b = fSet(t[u]);
//cout << u << endl;
while (a != b) {
if (h[a] < h[b]) swap(a, b);
uSet(par[a], a);
//a = fSet(a);
if (pos[a] != 0 && pos[a] != u && vst[pos[a]]) {
cout << "No" << endl;
return;
}
if (pot[a] != 0 && pot[a] != u && !vst[pot[a]]) {
cout << "No" << endl;
return;
}
if (pos[par[a]] != 0 && pos[par[a]] != u && vst[pos[par[a]]]) {
cout << "No" << endl;
return;
}
if (pot[par[a]] != 0 && pot[par[a]] != u && !vst[pot[par[a]]]) {
//cout << par[a] << endl;
cout << "No" << endl;
return;
}
a = fSet(a);
}
//ud(sta[t[u]], 1);
//ud(fin[t[u]] + 1, -1);
}
cout << "Yes" << endl;
//for (int u : topo) cout << u << " "; cout << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int test; cin >> test;
while (test--) 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... |