#include <bits/stdc++.h>
#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))
constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl
#define ll long long
#define pb push_back
using namespace std;
int n, m, mxLg;
vector<vector<int>> g, jp, g2, g2r;
vector<int> dep, vis, scc, post;
vector<pair<int, int>> st;
int tpost;
void dfs(int v, int p) {
jp[v][0] = p;
dep[v] = dep[p] + 1;
repIn(u, g[v]) if(u != p) dfs(u, v);
}
int lca(int x, int y) {
if(dep[x] > dep[y]) swap(x, y);
repD(i, mxLg - 1, -1) if(dep[jp[y][i]] >= dep[x]) y = jp[y][i];
if(x == y) return x;
repD(i, mxLg - 1, -1) if(jp[x][i] != jp[y][i]) x = jp[x][i], y = jp[y][i];
return jp[x][0];
}
void dfs2(int v) {
vis[v] = true;
repIn(u, g2[v]) if(!vis[u]) dfs2(u);
post[tpost++] = v;
}
void dfs3(int v, int c) {
scc[v] = c;
repIn(u, g2r[v]) if(!scc[u]) dfs3(u, c);
}
void solve() {
cin >> n;
g.resize(n + 1);
dep.resize(n + 1);
rep(i, 1, n) {
int a, b;
cin >> a >> b;
g[a].pb(b);
g[b].pb(a);
}
cin >> m;
st.resize(m);
rep(i, 0, m) cin >> st[i].first >> st[i].second;
mxLg = 32 - __builtin_clz(n);
jp.resize(n + 1, vector<int>(mxLg));
dfs(1, 1);
rep(k, 1, mxLg) rep(i, 1, n + 1) jp[i][k] = jp[jp[i][k - 1]][k - 1];
g2.resize(n * 2 * mxLg + m + 1);
g2r.resize(n * 2 * mxLg + m + 1);
rep(k, 0, mxLg - 1) rep(i, 1, n + 1) {
g2[n * 2 * k + i].pb(n * 2 * (k + 1) + i);
g2[n * 2 * k + jp[i][k]].pb(n * 2 * (k + 1) + i);
//g2[n * 2 * k + n + i].pb(n * 2 * (k + 1) + n + i);
//g2[n * 2 * k + n + jp[i][k]].pb(n * 2 * (k + 1) + n + i);
//g2[n * 2 * (k + 1) + i].pb(n * 2 * k + i);
//g2[n * 2 * (k + 1) + i].pb(n * 2 * k + jp[i][k]);
g2[n * 2 * (k + 1) + n + i].pb(n * 2 * k + n + i);
g2[n * 2 * (k + 1) + n + i].pb(n * 2 * k + n + jp[i][k]);
}
rep(i, 0, m) {
auto [s, t] = st[i];
auto mlca = lca(s, t);
g2[n * 2 * mxLg + 1 + i].pb(s);
g2[n + t].pb(n * 2 * mxLg + 1 + i);
repD(j, mxLg - 1, -1) if(dep[jp[s][j]] >= dep[mlca]) {
g2[n * 2 * j + s].pb(n * 2 * mxLg + i + 1);
g2[n * 2 * mxLg + i + 1].pb(n * 2 * j + n + s);
s = jp[s][j];
}
repD(j, mxLg - 1, -1) if(dep[jp[t][j]] >= dep[mlca]) {
g2[n * 2 * j + t].pb(n * 2 * mxLg + i + 1);
g2[n * 2 * mxLg + i + 1].pb(n * 2 * j + n + t);
t = jp[t][j];
}
}
rep(i, 0, (int)g2.size()) rep(j, 0, (int)g2[i].size()) {
DC << i << ' ' << g2[i][j] << eol;
g2r[g2[i][j]].pb(i);
}
vis.resize(g2.size());
post.resize(g2.size());
rep(i, 0, (int)g2.size()) if(!vis[i]) dfs2(i);
ranges::reverse(post);
scc.resize(g2.size());
repIn(i, post) if(!scc[i]) dfs3(i, i);
DC << eol;
rep(i, 1, (int)g2.size()) DC << i << ' ' << scc[i] << eol;
bool gg = true;
rep(i, 0, m) {
gg = gg && vis[scc[2 * n * mxLg + 1 + i]] >= 0;
vis[scc[2 * n * mxLg + 1 + i]] = -1;
}
cout << (gg ? "Yes" : "No") << '\n';
g.clear(); jp.clear(); g2.clear(); g2r.clear();
dep.clear(); vis.clear(); scc.clear(); post.clear();
st.clear();
tpost = 0;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int t;
cin >> t;
rep(i, 0, t) solve();
}
# | 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... |