#include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define rd read()

 using namespace std;

 const int N = ;

 const int base = ;

 int mp[N][N][N], f[N][N];

 int n, m;

 int read() {

     int X = , p = ; char c = getchar();

     for (; c > '' || c < ''; c = getchar())

         if (c == '-') p = -;

     for (; c >= '' && c <= ''; c = getchar())

         X = X *  + c - '';

     return X * p;

 }

 void cmin(int &A, int B) {

     if (A > B) A = B;

 }

 int main()

 {

     n = rd; m = rd;

     memset(f, , sizeof(f));

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

         int u = rd, v = rd;

         mp[u][v][] = ;

     }

     for (int dis = ; dis < base; ++dis)

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

             for (int i = ; i <= n; ++i) if (mp[i][k][dis - ])

                 for (int j = ; j <= n; ++j) if (mp[k][j][dis - ])

                     mp[i][j][dis] = ;

     for (int dis = ; dis < base; ++dis)

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

             for (int j = ; j <= n; ++j) if (mp[i][j][dis])

                 f[i][j] = ;

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

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

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

                 cmin(f[i][j], f[i][k] + f[k][j]);

     printf("%d\n", f[][n]);

 }