type node=record

        po,next,flow:longint;

      end;

 var e:array[..] of node;

     w,pre,numh,p,h,cur,x,y:array[..] of longint;

     ans,t,i,n,m,l,r,mid,len,need:longint;

 procedure add(x,y,f:longint);

   begin

     inc(len);

     e[len].po:=y;

     e[len].flow:=f;

     e[len].next:=p[x];

     p[x]:=len;

   end;

 procedure build(x,y,f1,f2:longint);

   begin

     add(x,y,f1);

     add(y,x,f2);

   end;

 function sap:longint;

   var i,j,q,u,tmp:longint;

   begin

     fillchar(numh,sizeof(numh),);

     fillchar(h,sizeof(h),);

     for i:= to t do

       cur[i]:=p[i];

     u:=; sap:=;

     while (h[]<t+) and (h[]<) do  //重要优化

     begin

       i:=cur[u];

       while i<>- do

       begin

         j:=e[i].po;

         if (e[i].flow>) and (h[u]=h[j]+) then

         begin

           cur[u]:=i;

           pre[j]:=u;

           u:=j;

           if u=t then

           begin

             inc(sap);

             if sap=need then exit;

             while u<> do

             begin

               u:=pre[u];

               j:=cur[u];

               dec(e[j].flow);

               inc(e[j xor ].flow);

             end;

           end;

           break;

         end;

         i:=e[i].next;

       end;

       if i=- then

       begin

         dec(numh[h[u]]);

         if numh[h[u]]= then exit;

         i:=p[u];

         tmp:=t;

         q:=-;

         while i<>- do

         begin

           j:=e[i].po;

           if e[i].flow> then

             if tmp>h[j] then

             begin

               q:=i;

               tmp:=h[j];

             end;

           i:=e[i].next;

         end;

         h[u]:=tmp+;

         inc(numh[h[u]]);

         cur[u]:=q;

         if u<> then u:=pre[u];

       end;

     end;

   end;

 procedure swap(var a,b:longint);

   var c:longint;

   begin

     c:=a;

     a:=b;

     b:=c;

   end;

 function check(h:longint):boolean;

   var i:longint;

   begin

     len:=-;

     fillchar(p,sizeof(p),);

     need:=;

     for i:= to n do

       w[i]:=h;

     for i:= to m do  //贪心初始流

     begin

       if w[x[i]]<w[y[i]] then swap(x[i],y[i]);

       if w[x[i]]= then

       begin

         build(i,x[i]+m,,);

         build(,i,,);

         inc(need);

       end

       else begin

         dec(w[x[i]]);

         build(,i,,);

         build(i,x[i]+m,,);

       end;

       build(i,y[i]+m,,);

     end;

     if need= then exit(true);

     for i:= to n do

       build(i+m,t,w[i],h-w[i]);

     if sap=need then exit(true) else exit(false);

   end;

 begin

   readln(n,m);

   for i:= to m do

   begin

     readln(x[i],y[i]);

     if w[x[i]]<w[y[i]] then inc(w[x[i]]) else inc(w[y[i]]);

   end;

   for i:= to n do

     if w[i]>r then r:=w[i];  //贪心上界

   t:=n+m+;

   l:=;

   while l<=r do

   begin

     mid:=(l+r) shr ;

     if check(mid) then

     begin

       ans:=mid;

       r:=mid-;

     end

     else l:=mid+;

   end;

   writeln(ans);

 end.