#include <cctype>

 #include <cstdio>

 #define REP(I,start,end) for(int I=(start);I<=(end);I++)

 #define PER(I,start,end) for(int I=(start);I>=(end);I--)

 inline int space()

 {

     return putchar(' ');

 }

 inline int enter()

 {

     return putchar('\n');

 }

 inline int getint()

 {

     char ch=getchar();

     for(;!isdigit(ch)&&ch!='+'&&ch!='-';ch=getchar());

     bool impositive=ch=='-';

     if(impositive)

         ch=getchar();

     int result=;

     for(;isdigit(ch);ch=getchar())

         result=(result<<)+(result<<)+ch-'';

     return impositive?-result:result;

 }

 template<typename integer> inline int write(integer n)

 {

     integer now=n;

     bool impositive=now<;

     if(impositive)

     {

         putchar('-');

         now=-now;

     }

     char sav[];

     sav[]=now%+'';

     int result=;

     for(;now/=;sav[result++]=now%+'');

     PER(i,result-,)

         putchar(sav[i]);

     return result+impositive;

 }

 template<typename T> inline bool getmax(T &target,T pattern)

 {

     return pattern>target?target=pattern,true:false;

 }

 template<typename T> inline bool getmin(T &target,T pattern)

 {

     return pattern<target?target=pattern,true:false;

 }

 //=====================Header Template=====================

 #pragma optimize(2)

 #include <algorithm>

 #include <cstring>

 #include <vector>

 using namespace std;

 typedef vector<int> vecint;

 typedef vecint::iterator vecnode;

 bool used[];

 int q[],label[],color[];

 vecint edge[],rec[];

 int main()

 {

     int n=getint();

     memset(edge,,sizeof(edge));

     for(int m=getint();m--;)

     {

         int u=getint(),v=getint();

         edge[u].push_back(v);

         edge[v].push_back(u);

     }

     REP(i,,n)

         sort(edge[i].begin(),edge[i].end());

     memset(used,,sizeof(used));

     memset(label,,sizeof(label));

     memset(rec,,sizeof(rec));

     int best=label[]=;

     REP(i,,n)

         rec[].push_back(i);

     REP(i,,n)

     {

         for(;;best-=rec[best].empty())

         {

             for(;!rec[best].empty()&&used[rec[best].back()];rec[best].pop_back());

             if(!rec[best].empty())

             {

                 used[q[i]=rec[best].back()]=true;

                 break;

             }

         }

         int now=q[i];

         for(vecnode it=edge[now].begin();it!=edge[now].end();it++)

         {

             int p=*it,pv=++label[p];

             rec[pv].push_back(p);

             getmax(best,pv);

         }

     }

     memset(color,,sizeof(color));

     int ans=;

     REP(i,,n)

     {

         int now=q[i];

         memset(used,,sizeof(used));

         for(vecnode it=edge[now].begin();it!=edge[now].end();it++)

             used[color[*it]]=true;

         REP(j,,n)

             if(!used[j])

             {

                 color[now]=j;

                 getmax(ans,j);

                 break;

             }

     }

     write(ans);

     enter();

     return ;

 }