题目链接：

pid=5305">传送门

题意：

n个人给定m个关系。每一个关系为x,y表示x,y是朋友。可是可能是online friends,也可能是offline friends.

要求每一个人的online 和offline 朋友的数量是一样多的，问有多少种可能。

分析：

n<=8， 因此m<=28.由题意能够知道。每一个人的关系数必须为偶数，然后我们能够枚举一个关系的状态，通过

每一个人的online,与offline关系数量小于等于1/2关系总数来剪枝。

代码例如以下：

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn = 10;

int du[maxn];

int n,m;

int on[maxn],off[maxn];

int edge[maxn*maxn][2];

int ans;

void dfs(int id){

    if(id==m){

        ans++;

        return;

    }

    on[edge[id][0]]++;

    on[edge[id][1]]++;

    if(on[edge[id][0]]*2<=du[edge[id][0]]&&on[edge[id][1]]*2<=du[edge[id][1]])

        dfs(id+1);

    on[edge[id][0]]--;

    on[edge[id][1]]--;

    off[edge[id][0]]++;

    off[edge[id][1]]++;

    if(off[edge[id][0]]*2<=du[edge[id][0]]&&off[edge[id][1]]*2<=du[edge[id][1]])

        dfs(id+1);

    off[edge[id][0]]--;

    off[edge[id][1]]--;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--){

        scanf("%d%d",&n,&m);

        ans=0;

        memset(du,0,sizeof(du));

        for(int i=0;i<m;i++){

            scanf("%d%d",&edge[i][0],&edge[i][1]);

            du[edge[i][0]]++;

            du[edge[i][1]]++;

        }

        bool tag = 0;

        if(m&1) tag=1;

        for(int i=1;i<=n;i++) if(du[i]&1) tag=1;

        if(tag){

            puts("0");

            continue;

        }

        memset(on,0,sizeof(on));

        memset(off,0,sizeof(off));

        dfs(0);

        printf("%d\n",ans);

    }

    return 0;

}