题目描述

有 n 个 城市，从 1 到 n 给他们编号，它们之间由一些单向道路（即一条道路只能从一个方向走向另一个方向，反之不行）相连，现在要求从 1 走到 n 。问最少经过几条路。

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

输入格式

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

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

输出格式

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

样例数据

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

2

数据规模

• 70% 的数据，$1≤n,m≤10^3$
• 100% 的数据，$1≤n,m≤10^5$