#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<string>

#include<cmath>

#include<queue>

#include<stack>

#include<map>

#include<utility>

#include<set>

#include<bitset>

#include<vector>

#include<ctime>

using namespace std;

typedef long long LL;

typedef double DB;

typedef pair<int,int> PII;

#define mmst(a,v) memset(a,v,sizeof(a))

#define mmcy(a,b) memcpy(a,b,sizeof(a))

#define re(i,a,b)  for(i=a;i<=b;i++)

#define red(i,a,b) for(i=a;i>=b;i--)

#define fi first

#define se second

template<class T>inline T sqr(T x){return x*x;}

template<class T>inline void upmin(T &t,T tmp){if(t>tmp)t=tmp;}

template<class T>inline void upmax(T &t,T tmp){if(t<tmp)t=tmp;}

const DB EPS=1e-;

inline int dblcmp(DB x){if(abs(x)<EPS)return ;return(x>)?:-;}

inline void SetOpen(string s)

  {

        freopen((s+".in").c_str(),"r",stdin);

        freopen((s+".out").c_str(),"w",stdout);

    }

inline int Getin_Int()

  {

        int res=,flag=;char z;

        for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());

        if(z==EOF)return ;

        if(z=='-'){flag=-flag;z=getchar();}

        for(;z!=EOF && isdigit(z);res=res*+z-'',z=getchar());

        return res*flag;

    }

inline LL Getin_LL()

  {

        LL res=,flag=;char z;

        for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());

        if(z==EOF)return ;

        if(z=='-'){flag=-flag;z=getchar();}

        for(;z!=EOF && isdigit(z);res=res*+z-'',z=getchar());

        return res*flag;

    }

const int maxN=;

const int maxM=;

int N,M;

PII a[maxM+];

int l,r,mid;

int first[maxN+],now=-;

struct Tedge{int v,next;}edge[*maxM+];

inline void addedge(int u,int v)

  {

        now++;

        edge[now].v=v;

        edge[now].next=first[u];

        first[u]=now;

    }

int form[maxM+];

int vis[maxM+];

inline int match(int x)

  {

        int i,v;

        for(i=first[x],v=edge[i].v;i!=-;i=edge[i].next,v=edge[i].v)

          if(!vis[v])

            {

                    vis[v]=;

                    if(form[v]==- || match(form[v]))

                      {

                            form[v]=x;

                            return ;

                        }

                }

        return ;

    }

inline int check(int mid)

  {

        int i;

        mmst(first,-);now=-;

        re(i,,mid){addedge(a[i].fi,i);addedge(a[i].se,i);}

        mmst(form,-);

        int tot=;

        re(i,,N)

          {

                mmst(vis,);

                if(match(i))tot++;

            }

        return tot==mid;

    }

int main()

  {

        int i;

        SetOpen("hero");

        N=Getin_Int();M=Getin_Int();

        re(i,,M)a[i].fi=Getin_Int()+,a[i].se=Getin_Int()+;

        l=,r=M;

        while(l<=r)

          {

                int mid=(l+r)/;

                if(check(mid))l=mid+; else r=mid-;

            }

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

        /*int tmp=check(r);

        re(i,1,r)printf("%d\n",form[i]-1);*/

        return ;

    }