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;
    }
}