Description

题目描述

金金要去赶集。集市上有 n 个 摊位，从 1 到 n 给这些摊位编号，这些摊位位于不同的岛上，摊位之间之间由一些单向道路（即一条道路只能从一个方向走向另一个方向，反之不行）相连，现在要求从第 1 个摊位走到第 n个摊位 。

金金想知道他自己最少经过几条路。

保证存在从 1到 n 的路径。

Input Format

输入格式

第一行两个整数 n 和 m，表示有多少个摊位点和多少条道路。

接下来 m 行，每行两个整数 s 、t ，即有一条从 s 到 t 的路。

Output Format

输出格式

一行一个整数，即从 1 到 n 最少经过几条路。

6 6 
1 3 
2 6 
3 6 
3 2 
6 4 
4 5​

2​

Hint

1<=n,m<1000

Source

图论