#include<bits/stdc++.h>
#define inf INT_MAX
#define ll long long
using namespace std;

bool ma[1010][1010],f[1010];
ll n,m,ans=inf;

ll check(ll x)
{
    ll k=0;
    while(x>0)
    {
        if(x%2==1) k++;
        x/=2;
    }
    return k;
}

 void dfs(ll x,ll y,ll k)
{   
    if(x==y)
    {
        ll t=check(k);
        if(t<ans) ans=t;
        return;
    }
    for(int i=1;i<=n;i++)
        if(ma[x][i] && !f[i])
        {
            f[x]=true;
            dfs(i,y,k+1);
            f[x]=false;
    	}
}

int main()
{
    scanf("%lld %lld",&n,&m);
    for(int i=1;i<=m;i++)
    {
        ll x,y;scanf("%lld %lld",&x,&y);
        ma[x][y]=true;
    }
    dfs(1,n,0);
    printf("%lld",ans);
    return 0;
}