#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#include<cmath>using namespace std;#define INF 2147483647#define MAXN 20011#define MAXM 100301int 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;}