156p 소풍

#include <iostream>

#include <vector>

#include <memory.h>

using namespace std;

int n,m;

int C;

bool areFriends[10][10],taken[10];

int countPairings(bool taken[10])

{

int firstFree = -1;

for(int i=0; i<n; i++)

{

if(!taken[i])

{

firstFree = i;

break;

}

}

if(firstFree == -1) return 1;

int ret = 0;

for(int pairWith = firstFree + 1; pairWith < n; pairWith++)

{

if(!taken[pairWith] && areFriends[firstFree][pairWith])

{

taken[firstFree] = taken[pairWith] = true;

ret += countPairings(taken);

taken[firstFree] = taken[pairWith] = false;

}

}

return ret;

}

int main()

{

cin>>C;

while(C--)

{

memset(areFriends, false, sizeof(areFriends));

cin>>n>>m;

int f1,f2;

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

{

cin>>f1>>f2;

areFriends[f1][f2] = true;

areFriends[f2][f1] = true;

}

cout<<countPairings(taken);

}

}