#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#include<cmath>

using namespace std;

#define INF 2147483647

#define MAXN 20011

#define MAXM 100301

int v[MAXM],cap[MAXM],en,first[MAXN],next[MAXM];

int d[MAXN],cur[MAXN];

queue<int>q;

int n,m,S,T;

void Init_Dinic(){memset(first,-1,sizeof(first)); en=0; S=0; T=n+m+1;}

void AddEdge(const int &U,const int &V,const int &W)

{v[en]=V; cap[en]=W; next[en]=first[U]; first[U]=en++;

v[en]=U; next[en]=first[V]; first[V]=en++;}

bool bfs()

{

    memset(d,-1,sizeof(d)); q.push(S); d[S]=0;

    while(!q.empty())

      {

        int U=q.front(); q.pop();

        for(int i=first[U];i!=-1;i=next[i])

          if(d[v[i]]==-1 && cap[i])

            {

              d[v[i]]=d[U]+1;

              q.push(v[i]);

            }

      }

    return d[T]!=-1;

}

int dfs(int U,int a)

{

    if(U==T || !a) return a;

    int Flow=0,f;

    for(int &i=cur[U];i!=-1;i=next[i])

      if(d[U]+1==d[v[i]] && (f=dfs(v[i],min(a,cap[i]))))

        {

          cap[i]-=f; cap[i^1]+=f;

          Flow+=f; a-=f; if(!a) break;

        }

    if(!Flow) d[U]=-1;

    return Flow;

}

int max_flow()

{

    int tmp=0,Flow=0;

    while(bfs())

      {

        memcpy(cur,first,(n+m+5)*sizeof(int));

        while(tmp=dfs(S,INF)) Flow+=tmp;

      }

    return Flow;

}

int us[10001],vs[10001];

void Rebuild(const int &x)

{

    Init_Dinic();

    for(int i=1;i<=m;++i)

      {

        AddEdge(S,i,1);

        AddEdge(i,us[i]+m,1);

        AddEdge(i,vs[i]+m,1);

      }

    for(int i=1;i<=n;++i) AddEdge(i+m,T,x);

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;++i) scanf("%d%d",&us[i],&vs[i]);

    int sz=sqrt(m); int last=0;

    for(int i=1;last<=m;i+=sz)

      {

        Rebuild(i);

        if(max_flow()>=m)

          {

            for(int j=last+1;j<=i;++j)

              {

                Rebuild(j);

                if(max_flow()>=m)

                  {

                    printf("%d\n",j);

                    return 0;

                  }

              }

          }

        last=i;

      }

    return 0;

}