1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <vector>
#include <cstring>
using std::vector;
int T, N, M, u, v;
vector<int> mat[10000];
bool b[10000], vis[10000];
bool dfs(int i, bool c) {
    if (vis[i])
        return b[i] == c;
    else {
        vis[i] = 1;
        b[i] = c;
        for (int k = 0; k < mat[i].size(); ++k)
            if (!dfs(mat[i][k], !c))
                return 0;
        return 1;
    }
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &N, &M);
        for (int i = 0; i < N; ++i)
            mat[i].clear();
        while (M--) {
            scanf("%d%d", &u, &v);
            --u, --v;
            mat[u].push_back(v);
            mat[v].push_back(u);
        }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX