wa#6

#include<bits/stdc++.h>
using namespace std;
int n,m,h[55],b[10005],nx[10005],tt,d[55];
bool f[55][55][33];
void zj(int x,int y)
{
	b[++tt]=y;
	nx[tt]=h[x];
	h[x]=tt;
}
void bfs()
{
	queue<int> q;
	q.push(1);
	d[1]=1;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=h[x];i;i=nx[i])
		{
			int y=b[i];
			if(d[y])
			continue;
			d[y]=d[x]+1;
			q.push(y);
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		f[x][y][0]=true;
	}
	for(int k=1;k<=32;k++)
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	for(int l=1;l<=n;l++)
	f[i][j][k]|=f[i][l][k-1]&f[l][j][k-1];
//	for(int i=1;i<=n;i++)
//	for(int j=1;j<=n;j++)
//	if(i!=j)
//	d[i][j]=10000000;
	for(int k=0;k<=32;k++) 
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	if(f[i][j][k])
	zj(i,j);
	bfs();
//	d[i][j]=1;
//	for(int k=1;k<=n;k++)
//	for(int i=1;i<=n;i++)
//	for(int j=1;j<=n;j++)
//	d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
	printf("%d",d[n]-1);
	return 0;
}