#include <bits/stdc++.h>
using namespace std;
long long int u[10001],v[10001],i,j,n,m,dis[10001],t[10001],s,t1[10001];
int main()
{
    cin>>n>>m;
    for(i=1;i<=m;i++)
        cin>>u[i]>>v[i];
    for(i=1;i<=n;i++)
        dis[i]=9999999;
    dis[1]=0;
    for(i=1;i<=n-1;i++)
        for(j=1;j<=m;j++)
        {
            s=1;
            dis[v[j]]=dis[u[j]]+1;
            if(t[v[j]]==0)
                while(dis[v[j]]!=0)
                {
                    if(dis[v[j]]-s>=0)
                        s=s*2;
                    else
                    {
                   dis[v[j]]=dis[v[j]]-s/2;
                        s=1;
                        t[v[j]]++;
                    }
                }
            else
            {
                while(dis[v[j]]!=0)
                {
                    if(dis[v[j]]-s>=0)
                        s=s*2;
                    else
                    {
                   dis[v[j]]=dis[v[j]]-s/2;
                        s=1;
                        t1[v[j]]++;
                    }
                }
                if(t1[v[j]]<t[v[j]])
                    t[v[j]]=t1[v[j]];
            }
        }
    cout<<t[n];
    return 0;
}