#9. 找最佳通路

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Chenyao

题目描述

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

保证存在从 11 1nnn 的路径。

输入格式

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

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

输出格式

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

样例

####输入样例

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

####样例输出

2

####样例解释

数据范围与提示

70%70\%70% 的数据,1≤n,m≤1031 \le n, m \le 10^31n,m103

100%100\%100% 的数据,1≤n,m≤1051 \le n,m \le 10^51n,m105