1 /*
 2 - 动态数组超时...... 
 3 */
 4 #include<iostream>
 5 #include<cstring>
 6 
 7 using namespace std;
 8 
 9 const int MAX = 109;
10 
11 // 邻接矩阵
12 int v[MAX][MAX];
13 // 考场里面的人
14 int room[MAX][MAX];
15 // 每个考场的人数
16 int len[MAX]; 
17 int n, m, ret = MAX;
18 
19 // 回溯 
20 void DFS(int x, int r)
21 {
22     // 多了这么一句剪枝, 就多通过的60%的数据... 
23     if(r >= ret) return;
24     if(x == n+1){
25         ret = min(r, ret);
26         return;
27     }
28     for(int i=1;i<=r;i++){
29         bool t = true;
30         int j = 0;
31         for(;j<len[i];j++){
32             if(v[x][room[i][j]]){ // 有认识的人 
33                 t = false;
34                 break;
35             }    
36         }
37         if(t){ // 没有认识的人 
38             len[i]++;
39             room[i][j] = x;
40             DFS(x+1, r);
41             len[i]--;
42             room[i][j] = 0;
43         } 
44     }
45     // 新开一间教室 
46     len[r+1]++;
47     room[r+1][0] = x;
48     DFS(x+1, r+1);
49     len[r+1]--;
50     room[r+1][0] = 0;
51 }
52 
53 int main()
54 {
55     while(cin>>n>>m)
56     {
57         int a, b;
58         memset(v, 0, sizeof(v));
59         memset(room, 0, sizeof(room));
60         memset(len, 0, sizeof(len));
61         while(m--)
62         {
63             scanf("%d%d", &a, &b);
64             v[a][b] = v[b][a] = 1;
65         }
66         // 最开始想从1号考场开始搜, 但是只能过80%
67         // 从0开始的话时间居然直接暴跌, 通过了... 
68         DFS(1, 0);
69         cout<<ret<<‘\n‘;
70     }
71     
72     return 0;
73 }