比较神奇的题。
定一个非叶子 \(r\) 为根。
显然只用判断两个叶子是否可达。
求出每个叶子向上能一步跳到的深度最浅的点 \(p_i\),那么如果 \(p_i\) 不在一条链上就无解,因为两条路径没有交点。
然后只用判断 \(p_i\) 最深的叶子的 \(p_i\) 能不能一步到达其他叶子即可。
code
// Problem: E. Bus Routes
// Contest: Codeforces - Codeforces Round 873 (Div. 1)
// URL: https://codeforces.com/problemset/problem/1827/E
// Memory Limit: 1024 MB
// Time Limit: 2500 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 500100;
int n, m, head[maxn], len, deg[maxn], b[maxn];
int fa[maxn], dep[maxn], son[maxn], sz[maxn], top[maxn];
bool vis[maxn];
pii a[maxn];
vector<int> vc[maxn];
struct edge {
int to, next;
} edges[maxn << 1];
inline void add_edge(int u, int v) {
edges[++len].to = v;
edges[len].next = head[u];
head[u] = len;
}
int dfs(int u, int f, int d) {
fa[u] = f;
sz[u] = 1;
dep[u] = d;
int maxson = -1;
for (int i = head[u]; i; i = edges[i].next) {
int v = edges[i].to;
if (v == f) {
continue;
}
sz[u] += dfs(v, u, d + 1);
if (sz[v] > maxson) {
son[u] = v;
maxson = sz[v];
}
}
return sz[u];
}
void dfs2(int u, int tp) {
top[u] = tp;
vis[u] = 1;
if (!son[u]) {
return;
}
dfs2(son[u], tp);
for (int i = head[u]; i; i = edges[i].next) {
int v = edges[i].to;
if (!vis[v]) {
dfs2(v, v);
}
}
}
inline int qlca(int x, int y) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) {
swap(x, y);
}
x = fa[top[x]];
}
if (dep[x] > dep[y]) {
swap(x, y);
}
return x;
}
void solve() {
len = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
head[i] = deg[i] = son[i] = 0;
vector<int>().swap(vc[i]);
vis[i] = 0;
}
for (int i = 1, u, v; i < n; ++i) {
scanf("%d%d", &u, &v);
add_edge(u, v);
add_edge(v, u);
++deg[u];
++deg[v];
}
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &a[i].fst, &a[i].scd);
vc[a[i].fst].pb(a[i].scd);
vc[a[i].scd].pb(a[i].fst);
}
if (n == 2) {
for (int i = 1; i <= m; ++i) {
if (a[i].fst != a[i].scd) {
puts("YES");
return;
}
}
puts("NO\n1 2");
return;
}
int r = -1;
for (int i = 1; i <= n; ++i) {
if (deg[i] > 1) {
r = i;
break;
}
}
dfs(r, -1, 1);
dfs2(r, r);
int p = -1, q = -1, mx = -1e9;
vector<pii> ps;
for (int u = 1; u <= n; ++u) {
if (deg[u] != 1) {
continue;
}
int k = -1, mn = 1e9;
if (vc[u].empty()) {
printf("NO\n%d %d\n", u, r);
return;
}
for (int v : vc[u]) {
int w = qlca(u, v);
if (dep[w] < mn) {
mn = dep[w];
k = w;
}
}
b[u] = k;
ps.pb(k, u);
if (dep[k] > mx) {
mx = dep[k];
p = k;
q = u;
}
}
sort(ps.begin(), ps.end(), [&](pii x, pii y) {
return dep[x.fst] < dep[y.fst];
});
for (int i = 0; i + 1 < (int)ps.size(); ++i) {
if (qlca(ps[i].fst, ps[i + 1].fst) != ps[i].fst) {
printf("NO\n%d %d\n", ps[i].scd, ps[i + 1].scd);
return;
}
}
for (int u = 1; u <= n; ++u) {
if (deg[u] != 1 || u == q) {
continue;
}
bool flag = 1;
for (int v : vc[u]) {
if (qlca(v, p) == p || qlca(u, p) == p) {
flag = 0;
break;
}
}
if (flag) {
printf("NO\n%d %d\n", u, q);
return;
}
}
puts("YES");
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}