非常有趣的结论题。
首先显然，整个图不是二分图就无解。
然后显然每个连通块独立，可以分连通块判定。
然后发现一度点是没什么用的，因为无论和它相连的点颜色是什么，它都能找到一种和这种颜色不同的颜色。所以考虑类似拓扑排序剥一度点。剩下的图的 \(deg_u \ge 2\)。
考虑若有一个偶环 \(1 \to 2 \to 3 \to 4 \to 1\)，可以 \(\{A, B\}, \{A, B\}, \{B, C\}, \{A, C\}\)，容易发现这样可以钦定 \(1\) 号点染 \(B\)。
所以若有两个仅交于一点或者不交的偶环就寄了，因为通过钦定一定可以导出矛盾。
进一步地，若有两个不重合部分点数 \(\ge 2\) 的偶环就寄了，因为可以让不公共部分放 \(\{B, C\}, \{A, C\}\)，公共部分放 \(\{A, B\}\)，也可以导出矛盾。
考虑如何快速判断这个东西。
不妨研究一下这个图的度数特点。考虑若存在两个度数 \(\ge 3\) 的点 \(u, v\)，取出任意三条 \(u \to v\) 的路径 \(P_1, P_2, P_3\)。
考虑若两条路径 \(P_1, P_2\) 存在除 \(u, v\) 外的交点 \(w_1, w_2, \ldots, w_k\)，那么让 \(u \to w_1 \to u, v \to w_k \to v\) 即可构造出无解（此时认为路径在第一个点和最后一个点不重合）。
所以 \(P_1, P_2, P_3\) 一定两两不交。不妨设 \(|P_1| \le |P_2| \le |P_3|\)（定义路径长度为经过的边数）。有解当且仅当 \(|P_1| = |P_2| = 2\)。
考虑存在度数 \(\ge 4\) 的点也寄了，因为要么其他点度数都 \(\ge 2\)（此时为两个重合于一点的环），要么存在一个点度数 \(\ge 3\)。
所以有解的充要条件为：
- 不存在度数 \(\ge 4\) 的点；
- 不存在度数 \(\ge 3\) 的点，或存在且仅存在两个度数 \(\ge 3\) 的点 \(x, y\)，使得存在至少两个度数 \(= 2\) 的点连接 \(x, y\)。
code
// Problem: P4429 [BJOI2018] 染色
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4429
// Memory Limit: 500 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 10050;
int n, m, a[maxn], fa[maxn], deg[maxn];
vector<int> G[maxn], vc[maxn];
bool e[maxn][maxn];
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
inline void merge(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
fa[x] = y;
}
}
bool dfs(int u) {
for (int v : G[u]) {
if (a[v] == -1) {
a[v] = a[u] ^ 1;
if (!dfs(v)) {
return 0;
}
} else if (a[v] == a[u]) {
return 0;
}
}
return 1;
}
void solve() {
mems(e, 0);
mems(a, -1);
mems(deg, 0);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
fa[i] = i;
vector<int>().swap(G[i]);
vector<int>().swap(vc[i]);
}
while (m--) {
int u, v;
scanf("%d%d", &u, &v);
G[u].pb(v);
G[v].pb(u);
merge(u, v);
++deg[u];
++deg[v];
e[u][v] = e[v][u] = 1;
}
for (int i = 1; i <= n; ++i) {
vc[find(i)].pb(i);
}
for (int i = 1; i <= n; ++i) {
if (a[i] == -1 && !dfs(i)) {
puts("NO");
return;
}
}
for (int _ = 1; _ <= n; ++_) {
if (vc[_].empty()) {
continue;
}
queue<int> q;
for (int i : vc[_]) {
if (deg[i] == 1) {
q.push(i);
}
}
while (q.size()) {
int u = q.front();
q.pop();
for (int v : G[u]) {
if ((--deg[v]) == 1) {
q.push(v);
}
}
}
int x = -1, y = -1;
for (int i : vc[_]) {
if (deg[i] >= 4) {
puts("NO");
return;
}
if (deg[i] == 3) {
if (x == -1) {
x = i;
} else if (y == -1) {
y = i;
} else {
puts("NO");
return;
}
}
}
if (x != -1) {
int cnt = 0;
for (int i : G[x]) {
if (deg[i] == 2 && e[x][i] == e[y][i]) {
++cnt;
}
}
if (cnt < 2) {
puts("NO");
return;
}
}
}
puts("YES");
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}