题解

#include <bits/stdc++.h>
using namespace std;

const int N = 10005;

vector<int> graph[N];
vector<int> colors(N);

bool dfs(int u, int color);
bool canColor(int n);

int main() {
    int T;
    cin >> T;
    while (T != 0) {
        int n, m;
        cin >> n >> m;
        
        for (int i = 1; i <= n; ++i) {
            graph[i].clear();
            colors[i] = 0;
        }
        
        for (int i = 0; i < m; ++i) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        
        if (canColor(n)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
        --T;
    }
    
    return 0;
}

bool dfs(int u, int color) {
    colors[u] = color;
    for (int v : graph[u]) {
        if (colors[v] == 0) {
            if (!dfs(v, 3 - color)) {
                return false;
            }
        } else if (colors[v] == color) {
            return false;
        }
    }
    return true;
}

bool canColor(int n) {
    for (int i = 1; i <= n; i++) {
        if (colors[i] == 0 && !dfs(i, 1)) {
            return false;
        }
    }
    return true;
}