//4. 分考场
//https://www.lanqiao.cn/problems/109/learning/?page=1&first_category_id=1&difficulty=20&second_category_id=3
//典型的dfs
//刚开始我想着是建图，认识的人之间没边，不认识的人之间有边，然后求“联通分量”（离散数学的概念）。其实大可不必，直接建图dfs即可，还是dfs联系的不熟练
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 110;

int n,m;//n个人m行数据
int f[N][N];//关系网
int g[N][N];//座位表，g[i][j]=k：表示第i个考场的第j个座位坐人k
int sum = N;//最终结果初始化为极大值

//要安排的第x个人，第y个考场
void  dfs(int per,int room)
{
  if(room>=sum) return;//这里去掉等于号，只能过60%
  if(per>n){
    sum = min(sum, room);
    return ;
  }

  //遍历考场
  for(int i=1;i<=room;i++){
    int k = 1;
    //注意这里的判断逻辑，是判断当前这个人per，是否认识当前教室room里的人
    //所以一个变量为k，一个变量为g[i][k]
    while(!f[per][g[i][k]] && g[i][k]) k++;

    if(g[i][k] == 0){
      g[i][k] = per;//安排per坐下

      dfs(per+1, room);//接着遍历下一个人，教室数量还是目前这个教室数量

      g[i][k] = 0;//回溯
    }else{
      continue;//如果目前这个人per，认识目前教室room里的人，则访问下一个room
    }
  }

  g[room+1][1] = per;//新开一个教室，第一个位置坐人per
  dfs(per+1, room+1);
  g[room+1][1] = 0;//回溯
}

signed main()
{
  // 请在此输入您的代码
  cin>>n>>m;
  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    f[a][b] = f[b][a] = 1;
  }

  dfs(1,1);

  cout<<sum<<endl;

  return 0;
}