#include <iostream>

#include <vector>

#include <queue>

#include <cstring>

#define maxn 55

using namespace std;

int n, m;

int g[maxn][maxn];

bool avai[maxn][maxn][];

int main()

{

    ios::sync_with_stdio(false);

    memset(g, 0x3f, sizeof(g));

    cin >> n >> m;

    int u, v;

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

    {

        cin >> u >> v;

        avai[u][v][] = g[u][v] = ;

    }

    for (int i = ; i <= n; i++)

        g[i][i] = ;

    //f(i,j,k)=f(i,v,k-1)&&f(v,j,k-1)

    for (int k = ; k <= ; k++)

    {

        for (int u = ; u <= n; u++)

        {

            for (int v = ; v <= n; v++)

            {

                for (int w = ; w <= n; w++)

                {

                    if (avai[u][v][k] |= avai[u][w][k - ] ==  && avai[w][v][k - ] == )

                        g[u][v] = ;

                }

            }

        }

    }

    for (int k = ; k <= n; k++)

        for (int i = ; i <= n; i++)

            for (int j = ; j <= n; j++)

                g[i][j] = min(g[i][k] + g[k][j], g[i][j]);

    cout << g[][n] << endl;

    return ;

}