7.23多校——5305DFS——Friends

/*
cnt1[i]表示i顶点编号为1的度数
cnt2[i]表示i顶点编号为2的度数
显然得到如果存在一个点的度数为奇数，那么输出0（要平分）
如果顶点度数都是偶数,进行dfs，dfs边的数目，终止条件为cur == m （从0开始）
判断之前添的边能否满足
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int n,m;
int cnt1[10], cnt2[10];
pair <int, int > a[100];

int ret;

bool check(int x)
{
    for(int i = 1; i <= x; i++){
        if(cnt1[i] != cnt2[i])
                return false;
    }
     return true;
}

void dfs(int cur)
{
    if(cur == m ){
        if(check(n))
            ret++;
        return ;
    }
    int u = a[cur].first;
    int v = a[cur].second;
    cnt1[u]++;
    cnt1[v]++;
    if(check(u-1)){
        dfs(cur + 1);
    }
    cnt1[u]--;
    cnt1[v]--;
    cnt2[u]++;
    cnt2[v]++;
    if(check(u-1)){
        dfs(cur + 1);
    }
    cnt2[u]--;
    cnt2[v]--;
}

int main()
{
    int T;
    int x, y;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &m);
        memset(cnt1, 0, sizeof(cnt1));
        memset(cnt2, 0, sizeof(cnt2));
        for(int i = 0; i < m ; i++){
            scanf("%d%d", &x, &y);
            if( x > y)
                swap(x, y);
            cnt1[x]++;
            cnt1[y]++;
            a[i] = make_pair(x, y);
        }
        int flag = 0;
        sort(a , a + m );
        for(int i = 1; i <= n ;i++)
            if(cnt1[i] % 2 == 1){
                flag = 1;
                break;
            }
        memset(cnt1, 0, sizeof(cnt1));
        ret = 0;
        dfs(0);
        if(flag == 0) printf("%d\n", ret);
        else printf("0\n");
    }
    return 0;
}