无向图判断欧拉回路

//
//  oula.cpp
//  666
//
//  Created by Terry on 2018/7/6.
//  Copyright © 2018年 Terry. All rights reserved.
//  如果无向图连通并且所有结点的度都是偶数，则存在欧拉回路，否则不存在。


#include <iostream>
#include <cstring>
#include <algorithm>
#define mst(a, b) memset((a), (b), sizeof(a))
using namespace std;
const int maxn = 1000 + 100;
int graph[maxn][maxn];
bool vis[maxn];
int InDeg[maxn];
int n, m, sum;
void init(){
    mst(vis, 0);
    mst(graph, 0);
    mst(InDeg, 0);
}
void dfs(int k){
    vis[k] = 1;
    sum++;
    for(int i = 1; i <= n; i++){
        if(!vis[i] && graph[k][i]){
            vis[i] = 0;
            dfs(i);
        }
    }
}
int main(){
    int T;
    scanf("%d", &T);
    for(int Case = 1; Case <= T; ++Case){
        init();
        int u, v;
        scanf("%d%d", &n, &m);
        while(m--){
            scanf("%d%d", &u, &v);
            graph[u][v] = 1;
            InDeg[u]++;
            InDeg[v]++;
        }
        dfs(u); // 判断 图是否联通
        bool flag = 1;
        for(int i = 1; i <= n; i++){
            if(InDeg[i] % 2 != 0){
                flag = 0;
                break;
            }
        }
        if(sum == n && flag){
            puts("1");
        }
        else{
            puts("0");
        }
    }
    return 0;
}