#573. 找最佳通路

找最佳通路

题目描述

nn 个 城市,从 11nn 给他们编号,它们之间由一些单向道路(即一条道路只能从一个方向走向另一个方向,反之不行)相连,现在要求从 11 走到 nn 。问最少经过几条路。

保证存在从 11 nn 的路径。

输入格式

第一行两个整数 nnmm,表示有多少个城市和多少条道路。

接下来 mm 行,每行两个整数 sstt ,即有一条从 sstt 的路。

输出格式

一行一个整数,即从 11nn 最少经过几条路。

样例

输入样例

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

样例输出

2

样例解释

数据范围与提示

70%70\% 的数据,1n,m1031 \le n, m \le 10^3

100%100\% 的数据,1n,m1051 \le n,m \le 10^5