import java.util.*;
/*
* public class Point {
* int x;
* int y;
* }
*/
public class Solution {
/**
* 返回新集合的种类数
* @param n int整型 集合大小
* @param m int整型 限制数量
* @param limit Point类一维数组 不能同时出现的(u,v)集合
* @return int整型
*/
int cnt=0;
public int solve (int n, int m, Point[] limit) {
// write code here
int[] arr=new int[n];
return com(arr,limit,n);
}
private int com(int[] arr ,Point[] limit,int n){
if(n==0) {
if(isok(arr,limit)){
return 1;
}else{
return 0;
}
}else{
int[] arr0=arr.clone();
int[] arr1=arr.clone();
arr1[n-1]=n;
return com(arr0,limit,n-1)+com(arr1,limit,n-1);
}
}
private boolean isok(int[] arr,Point[] limit){
int x,y;
boolean flagx;
boolean flagy;
for (int i = 0; i < limit.length; i++) {
x=limit[i].x;
y=limit[i].y;
flagx=false;
flagy=false;
for (int j = 0; j < arr.length; j++) {
if(arr[j]==x) flagx=true;
if(arr[j]==y) flagy=true;
if(flagx&&flagy)return false;
}
}
return true;
}
}