/*

给定一个n个点m条边的有向图，图中可能存在重边和自环。

所有边的长度都是1，点的编号为1~n。

请你求出1号点到n号点的最短距离，如果从1号点无法走到n号点，输出-1。

输入格式： 

第一行包含两个整数n和m。

接下来m行，每行包含两个整数a和b，表示存在一条从a走到b的长度为1的边。

输出格式： 

输出一个整数，表示1号点到n号点的最短距离。

数据范围： 

1≤n,m≤105

输入样例：

4 5

1 2

2 3

3 4

1 3

1 4

输出样例：

1

 

 

注意：1.数与图的遍历，该题为有向图 ，邻接表 

   2.d[]为距离，q[]为队列 

   3. bfs求最短路 

*/

 

 

#include<bits/stdc++.h>

using namespace std;

queue<int>q;

const int N=1e6+10;

int e[N*2],ne[N*2],h[N],idx;//邻接表 

int d[N],n,m,a,b;

void add(int a,int b)//a->b的边 

{

 e[idx]=b,ne[idx]=h[a],h[a]=idx++;

}

int bfs()

{

 memset(d,-1,sizeof(d));

 q.push(1);//1号元素加入队列 

 d[1]=0;//1号元素到自身的距离为0 

 while(q.size())//当队列不空 

 {

  int t=q.front();//取得队头 

  q.pop();

  for(int i=h[t];i!=-1;i=ne[i])

  {

   int j=e[i];//扩展 

   if(d[j]==-1)//未遍历过

   {

    d[j]=d[t]+1;//扩展 

    q.push(j);//插入 

   }

  }

 }

 return d[n];

}

int main()

{

 memset(h,-1,sizeof(h));//头插法，使得邻接表的尾节点都为-1 

 scanf("%d%d",&n,&m);

 while(m--)

 {

  scanf("%d%d",&a,&b);

  add(a,b);//有向图 

 }

 printf("%d",bfs());

 return 0;

}