#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
// Cấu hình giới hạn
const int MAXN = 120005;
const int LOG = 18; // 2^17 > 120000
const int MAX_NODES = MAXN * LOG * 2 + MAXN + 50000;
const int MAX_EDGES = MAX_NODES * 4;
// Biến toàn cục cho Đồ thị ban đầu (Cây)
vector<int> adj[MAXN];
int up[MAXN][LOG];
int depth[MAXN];
int N, M;
// Biến toàn cục cho Đồ thị phụ thuộc (Virtual Graph)
// Dùng mảng tĩnh để tiết kiệm bộ nhớ và thời gian (Thay cho vector<vector>)
int head[MAX_NODES], nxt[MAX_EDGES], to[MAX_EDGES];
int deg[MAX_NODES];
int edge_cnt = 0;
int total_nodes = 0;
void add_edge(int u, int v) {
to[++edge_cnt] = v;
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
deg[v]++;
}
// DFS để dựng Binary Lifting
void dfs(int u, int p, int d) {
depth[u] = d;
up[u][0] = p;
for (int k = 1; k < LOG; ++k) {
up[u][k] = up[up[u][k-1]][k-1];
}
for (int v : adj[u]) {
if (v != p) dfs(v, u, d + 1);
}
}
int get_lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
for (int k = LOG - 1; k >= 0; --k) {
if (depth[u] - (1 << k) >= depth[v]) u = up[u][k];
}
if (u == v) return u;
for (int k = LOG - 1; k >= 0; --k) {
if (up[u][k] != up[v][k]) {
u = up[u][k];
v = up[v][k];
}
}
return up[u][0];
}
// Hàm lấy ID node ảo
// id: 1..M (Prisoners)
// SRC: M + (u-1)*LOG + k + 1
// SNK: M + N*LOG + (u-1)*LOG + k + 1
inline int ID_SRC(int u, int k) {
return M + (u - 1) * LOG + k + 1;
}
inline int ID_SNK(int u, int k) {
return M + N * LOG + (u - 1) * LOG + k + 1;
}
// Nối các đoạn phủ đường đi u -> ancestor vào tù nhân id
// Type 0: Source (Segment -> id), Type 1: Sink (id -> Segment)
void connect_path(int u, int ancestor, int id, int type) {
int d = depth[u] - depth[ancestor]; // Số bước cần nhảy
for (int k = LOG - 1; k >= 0; --k) {
if ((d >> k) & 1) {
// Đoạn (u, 2^k)
if (type == 0) add_edge(ID_SRC(u, k), id);
else add_edge(id, ID_SNK(u, k));
u = up[u][k];
}
}
}
void solve() {
if (!(cin >> N)) return;
// Reset dữ liệu cây
for (int i = 1; i <= N; ++i) adj[i].clear();
for (int i = 0; i < N - 1; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 1, 0);
cin >> M;
vector<pair<int, int>> prisoners(M + 1);
// Reset đồ thị ảo
total_nodes = M + 2 * N * LOG;
edge_cnt = 0;
// Fill mảng head và deg cẩn thận
// Vì total_nodes khá lớn, dùng vòng lặp reset thay vì memset toàn bộ mảng MAX
for(int i=0; i<=total_nodes; ++i) {
head[i] = 0;
deg[i] = 0;
}
// Xây dựng khung Doubling
for (int u = 1; u <= N; ++u) {
for (int k = 1; k < LOG; ++k) {
// Source: Con trỏ đến Cha (Gộp dòng chảy)
int src_curr = ID_SRC(u, k);
int src_prev = ID_SRC(u, k-1);
int src_jump = ID_SRC(up[u][k-1], k-1);
add_edge(src_prev, src_curr);
add_edge(src_jump, src_curr);
// Sink: Cha trỏ đến Con (Phân tán dòng chảy)
int snk_curr = ID_SNK(u, k);
int snk_prev = ID_SNK(u, k-1);
int snk_jump = ID_SNK(up[u][k-1], k-1);
add_edge(snk_curr, snk_prev);
add_edge(snk_curr, snk_jump);
}
}
for (int i = 1; i <= M; ++i) {
int s, t;
cin >> s >> t;
prisoners[i] = {s, t};
// Liên kết tù nhân với vị trí cụ thể (k=0)
add_edge(i, ID_SRC(s, 0)); // i đến từ S_i
add_edge(ID_SNK(t, 0), i); // i đi đến T_i
int lca = get_lca(s, t);
// Xử lý Source (Ai đang chắn đường i?) -> Query path(S -> T) trừ S
// Nhánh S -> LCA (trừ S): Nhảy lên 1 bước từ S rồi query
if (s != lca) {
connect_path(up[s][0], lca, i, 0); // S->LCA hướng lên
add_edge(ID_SRC(lca, 0), i); // Thêm đỉnh LCA
}
// Nhánh T -> LCA (trừ LCA): Vì đây là đường đi của i,
// và Source check là "Ai xuất phát trên đường này".
// Đường đi là S->...->LCA->...->T.
// Phần T->LCA thực chất là query các node từ T ngược về con của LCA.
// Logic connect_path luôn query đường lên (node -> ancestor).
// Đường từ LCA xuống T cũng là tập hợp các node trên đường thẳng đứng từ T lên LCA.
// Ta query từ T lên con của LCA.
if (t != lca) {
// Query T lên LCA, nhưng LCA đã add ở trên, nên chỉ lên đến con của LCA?
// Không, connect_path(T, LCA, ...) sẽ bao gồm cả LCA.
// Cần cẩn thận không add trùng LCA 2 lần nếu không cần thiết (dù add trùng ko sao).
// Nhưng quan trọng: path Source cover toàn bộ node trên S->T ngoại trừ S.
// connect_path(T, LCA, i, 0) sẽ cover từ T lên LCA.
// LCA đã được cover ở nhánh S.
// Để đơn giản và tránh self-loop i->i, ta cần loại bỏ S. S nằm ở nhánh 1.
// Nhánh 2 là T->LCA. Không chứa S. An toàn.
connect_path(t, lca, i, 0);
// Lưu ý: connect_path(u, anc) bao gồm cả u và anc.
// Vậy LCA được add 2 lần. Không sao.
} else {
// Nếu S == LCA, đường đi là dốc xuống S -> T.
// Nhánh 1 rỗng (vì bỏ S).
// Nhánh 2 là T -> S. Cover path từ T lên S.
// Vì bỏ S (là điểm xuất phát), ta dùng connect_path(T, S, ...) nhưng bỏ S?
// connect_path phủ từ T lên S. Ta chỉ cần dừng trước S.
// Nhưng hàm connect_path của mình phủ cả ancestor.
// Hack nhẹ: tách node LCA ra xử lý riêng hoặc chấp nhận query dư (nhưng phải bỏ S).
// Cách xử lý chính xác để BỎ S và BỎ T:
// Path S -> T.
// SOURCE: Cần cover (S_next -> T).
// SINK: Cần cover (S -> T_prev).
}
}
// Logic lại phần Connect Path chuẩn xác để tránh Self-Loop
// Reset edge cho chắc và viết lại đoạn loop trên
// (Đoạn dưới đây thay thế đoạn loop i=1..M ở trên)
}
// Hàm giải quyết chính xác logic path
void solve_exact() {
if (!(cin >> N)) return;
for (int i = 1; i <= N; ++i) adj[i].clear();
for (int i = 0; i < N - 1; ++i) {
int u, v; cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
}
dfs(1, 1, 0);
cin >> M;
total_nodes = M + 2 * N * LOG;
edge_cnt = 0;
for(int i=0; i<=total_nodes; ++i) { head[i] = 0; deg[i] = 0; }
for (int u = 1; u <= N; ++u) {
for (int k = 1; k < LOG; ++k) {
add_edge(ID_SRC(u, k-1), ID_SRC(u, k));
add_edge(ID_SRC(up[u][k-1], k-1), ID_SRC(u, k));
add_edge(ID_SNK(u, k), ID_SNK(u, k-1));
add_edge(ID_SNK(u, k), ID_SNK(up[u][k-1], k-1));
}
}
for(int i=1; i<=M; ++i){
int s, t; cin >> s >> t;
// Liên kết cơ bản
add_edge(i, ID_SRC(s, 0));
add_edge(ID_SNK(t, 0), i);
int lca = get_lca(s, t);
// 1. SOURCE Constraints (j -> i): Path S->T excluding S
// Nhánh S -> LCA: Bắt đầu từ up[s][0] (để bỏ S) lên tới LCA
if(s != lca) connect_path(up[s][0], lca, i, 0);
// Nhánh T -> LCA: Từ T lên tới child của LCA (để tránh LCA nếu đã add, hoặc add cả LCA cũng dc)
// Tuy nhiên, path từ S->T đi qua LCA. LCA không phải là S (trừ khi S=LCA).
// Nếu S!=LCA, LCA đã được add ở dòng trên.
// Nếu S==LCA, dòng trên không chạy. Ta cần add LCA ở dòng dưới? Không, LCA là S, phải bỏ S.
// Vậy:
// Nếu S != LCA: Add path(up[S], LCA).
// Nhánh T: Add path(T, LCA) nhưng bỏ LCA (để tránh trùng).
// Hoặc đơn giản: Add path(T, LCA). LCA bị tính 2 lần không sao.
// NHƯNG nếu S=LCA, path(T, LCA) sẽ chứa LCA=S -> Sai (phải bỏ S).
// Fix:
// Path 1 (S hướng lên): nếu S!=LCA, connect(up[S], LCA). (Bao gồm LCA).
// Path 2 (T hướng lên): connect(T, ...).
// Điểm gặp nhau là LCA.
// Nếu S == LCA: Cần cover toàn bộ T -> LCA ngoại trừ LCA. => connect(T, child_of_LCA_on_T_branch?).
// Khó tìm child.
// Đơn giản hơn: connect(T, LCA). Nếu S==LCA thì không add cạnh nối từ node ảo LCA vào i?
// Không được, node ảo LCA chứa nhiều người khác.
// GIẢI PHÁP TỐI ƯU: Sử dụng hàm connect_path linh hoạt (exclude ancestor)
// Add SOURCE
if (s != lca) {
connect_path(up[s][0], lca, i, 0); // Include LCA
}
// Nhánh bên T: đi từ T lên LCA.
// Nếu S == LCA, ta phải bỏ LCA. -> connect(T, strict_child_of_LCA).
// Nếu S != LCA, ta có thể lấy cả LCA (trùng k sao).
// Để tổng quát: Luôn lấy T -> LCA.
// TRỪ TRƯỜNG HỢP S==LCA thì phải xử lý LCA riêng (không add).
// Nhưng connect_path lại add theo đoạn.
// Cách dễ nhất: Add T -> LCA.
// Nếu S == LCA, ta xóa cạnh SRC(LCA, 0) -> i ? Không thể.
// Ta dùng ID_SRC(u, k) -> i.
// S==LCA nghĩa là i xuất phát tại LCA.
// Cạnh i -> SRC(LCA, 0) đã có.
// Nếu ta add SRC(LCA, ...) -> i, ta tạo chu trình.
// Vậy khi add Source path cho i, ta TUYỆT ĐỐI không được đụng vào node ảo chứa S.
// Node ảo (u, k) chứa S nếu u == S hoặc u là con cháu S... sai.
// Node ảo (u, k) đại diện cho đoạn từ u ngược lên 2^k.
// Nó chứa S nếu S nằm trong đoạn đó.
// Chốt:
// Nhánh S -> LCA: Đi từ up[s][0] lên LCA. (An toàn, vì đoạn này nằm trên S hẳn).
// Nhánh T -> LCA: Đi từ T lên LCA.
// Đoạn này chứa LCA.
// Nếu S == LCA, đoạn này chứa S -> tạo chu trình.
// Vậy nếu S == LCA, ta chỉ được đi từ T lên đến "con của LCA".
// Để làm điều này, ta nhảy T lên đến khi depth = depth[LCA] + 1.
if (depth[t] > depth[lca]) {
int t_jump = t;
// Nhảy t_jump lên sát LCA
for(int k=LOG-1; k>=0; --k){
if(depth[t_jump] - (1<<k) > depth[lca]) t_jump = up[t_jump][k];
}
// t_jump bây giờ là con trực tiếp của LCA
connect_path(t, t_jump, i, 0); // Add từ T lên sát LCA
// Còn bản thân LCA?
// Nếu S != LCA, ta cần add LCA. (Đã add ở nhánh S->LCA).
// Nếu S == LCA, ta không add LCA.
// Logic này đúng hoàn toàn!
}
// 2. SINK Constraints (i -> j): Path S->T excluding T
// Tương tự, ta cần bỏ T.
// Nhánh S -> LCA: Đi từ S lên LCA.
// Nếu T == LCA, phải bỏ LCA. -> Chỉ đi S lên sát LCA.
if (depth[s] > depth[lca]) {
int s_jump = s;
for(int k=LOG-1; k>=0; --k){
if(depth[s_jump] - (1<<k) > depth[lca]) s_jump = up[s_jump][k];
}
connect_path(s, s_jump, i, 1);
}
// Nhánh T -> LCA: Bỏ T, tức là đi từ up[T][0] lên LCA.
// Nếu T != LCA:
if (t != lca) {
connect_path(up[t][0], lca, i, 1); // Include LCA
}
// Nếu T == LCA, nhánh này rỗng (đúng). Và nhánh S->LCA ở trên đã bỏ LCA (đúng).
}
// Topo Sort
queue<int> q;
for(int i=1; i<=total_nodes; ++i) {
if(deg[i] == 0) q.push(i);
}
int processed = 0;
while(!q.empty()){
int u = q.front(); q.pop();
processed++;
int e = head[u];
while(e){
int v = to[e];
deg[v]--;
if(deg[v] == 0) q.push(v);
e = nxt[e];
}
}
if(processed == total_nodes) cout << "Yes\n";
else cout << "No\n";
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int Q;
if (cin >> Q) {
while (Q--) solve_exact();
}
return 0;
}
