Friends
有 n 个人，m 组朋友，要求每个人有一半的朋友在线，一半的朋友不在线 ，求多少种可能。
如果一个人有奇数个朋友，显然是不成立的
若都有偶数个，我们先假设两种状态的朋友各有一半，然后借用 m 种关系，使得其成立即可
const int N=100+5;
int n,m,t;
int i,j,k;
int a[N],b[N];
int num[N];
Pair G[N];
int ans;
void DFS(int step)
{
if(step==m+1){ ans++; return ;}
int x=G[step].fr,y=G[step].sc;
if(a[x] && a[y]){ //朋友 x，y在线
a[x]--;
a[y]--;
DFS(step+1);
a[x]++;
a[y]++;
}
if(b[y] && b[x]){ //朋友 x,y下线
b[y]--;
b[x]--;
DFS(step+1);
b[x]++;
b[y]++;
}
return ;
}
int main()
{
IOS;
rush(){
cin>>n>>m;
ms(G,0);
ms(num,0);
for(i=1;i<=m;i++){
cin>>G[i].fr>>G[i].sc;
num[G[i].fr]++;
num[G[i].sc]++;
}
bool flag=0;
for(i=1;i<=n;i++){
a[i]=b[i]=num[i]/2;
if(num[i]&1){
flag=1;
break;
}
}
if(flag){ cout<<0<<endl; continue; }
ans=0;
DFS(1);
cout<<ans<<endl;
}
//PAUSE;
return 0;
}
