1 /* 2     题意：每个点都要有偶数条边，且边染色成相同的两部分，问能有多少种染色方法 3     DFS+剪枝：按照边数来DFS，每种染色数为该点入度的一半，还有如果点不是偶数边就不DFS 4             这是别人的DFS，写的精简强大，膜拜之。。。 5 */ 6 #include 
     
       7 #include 
      
        8 #include 
       
         9 #include 
        
         10 using namespace std;11 12 const int MAXN = 33;13 const int INF = 0x3f3f3f3f;14 int d[MAXN], c1[MAXN], c2[MAXN];15 int a[MAXN], b[MAXN];16 int n, m, ans;17 18 void DFS(int k) {19     if (k == m + 1) {20         ans++;  return ;21     }22     int u = a[k], v = b[k];23     if (c1[u] < d[u] && c1[v] < d[v])   {24         c1[u]++;    c1[v]++;25         DFS (k + 1);26         c1[u]--;    c1[v]--;27     }28     if (c2[u] < d[u] && c2[v] < d[v])   {29         c2[u]++;    c2[v]++;30         DFS (k + 1);31         c2[u]--;    c2[v]--;32     }33 }34 35 int main(void)  {       //HDOJ 5305 Friends36     //freopen ("F.in", "r", stdin);37 38     int t;  scanf ("%d", &t);39     while (t--) {40         memset (d, 0, sizeof (d));41         scanf ("%d%d", &n, &m);42         for (int i=1; i<=m; ++i)    {43             scanf ("%d%d", &a[i], &b[i]);44             d[a[i]]++; d[b[i]]++;45         }46         47         bool flag = true;48         for (int i=1; i<=n; ++i)    {49             if (d[i] & 1)   {50                 flag = false;   break;51             }52             d[i] /= 2;53         }54 55         if (!flag)  {56             puts ("0"); continue;57         }58         memset (c1, 0, sizeof (c1));59         memset (c2, 0, sizeof (c2));60         ans = 0;    DFS (1);61         printf ("%d\n", ans);62     }63 64     return 0;65 }