CF1693C.Keshi in Search of AmShZ

AmShZ has traveled to Italy from Iran for the Thom Yorke concert. There are $n$ cities in Italy indexed from $1$ to $n$ and $m$ directed roads indexed from $1$ to $m$. Initially, Keshi is located in the city $1$ and wants to go to AmShZ's house in the city $n$. Since Keshi doesn't know the map of Italy, AmShZ helps him to see each other as soon as possible.

In the beginning of each day, AmShZ can send one of the following two messages to Keshi:

• AmShZ sends the index of one road to Keshi as a blocked road. Then Keshi will understand that he should never use that road and he will remain in his current city for the day.

• AmShZ tells Keshi to move. Then, Keshi will randomly choose one of the cities reachable from his current city and move there. (city $B$ is reachable from city $A$ if there's an out-going road from city $A$ to city $B$ which hasn't become blocked yet). If there are no such cities, Keshi will remain in his current city.

  Note that AmShZ always knows Keshi's current location.

AmShZ and Keshi want to find the smallest possible integer $d$ for which they can make sure that they will see each other after at most $d$ days. Help them find $d$.

AmShZ 为了观看 Thom Yorke 的演唱会，从伊朗来到了意大利。意大利共有 $n$ 座城市，编号从 $1$ 到 $n$，以及 $m$ 条有向道路，编号从 $1$ 到 $m$。初始时，Keshi 位于城市 $1$，他希望前往位于城市 $n$ 的 AmShZ 家中。由于 Keshi 不熟悉意大利的地图，AmShZ 帮助他尽快与自己见面。

每天开始时，AmShZ 可以向 Keshi 发送以下两种消息之一：

• AmShZ 向 Keshi 发送一条被封锁道路的编号。随后，Keshi 将明白他永远不应使用该道路，并在当天停留在当前所在城市。
• AmShZ 告知 Keshi 移动。随后，Keshi 将随机选择一个从其当前城市出发、可通过的（即尚未被封锁的）有向道路所能到达的城市，并移动到该城市。（若存在从城市 $A$ 到城市 $B$ 的一条尚未被封锁的出边，则称城市 $B$ 从城市 $A$ 可达。）若不存在这样的城市，Keshi 将停留在当前城市。

注意：AmShZ 始终知晓 Keshi 当前所处的位置。

AmShZ 和 Keshi 希望找到最小的正整数 $d$，使得他们能够确保在至多 $d$ 天内彼此相见。请帮助他们求出 $d$。

The first line of the input contains two integers $n$ and $m$ $(2 \le n \le 2 \cdot 10^5, 1 \le m \le 2 \cdot 10^5)$ — the number of cities and roads correspondingly.

The $i$-th line of the following $m$ lines contains two integers $v_i$ and $u_i$ $(1 \le v_i , u_i \le n,v_i \neq u_i)$, denoting a directed road going from city $v_i$ to city $u_i$.

It is guaranteed that there is at least one route from city $1$ to city $n$. Note that there may be more than one road between a pair of cities in each direction.

输入的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 2 \cdot 10^5$，$1 \le m \le 2 \cdot 10^5$），分别表示城市的数量和道路的数量。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $v_i$ 和 $u_i$（$1 \le v_i , u_i \le n$，且 $v_i \neq u_i$），表示一条从城市 $v_i$ 指向城市 $u_i$ 的有向道路。

保证至少存在一条从城市 $1$ 到城市 $n$ 的路径。注意：在每一对城市之间，每个方向上可能存在多条道路。

Output the smallest possible integer $d$ to make sure that AmShZ and Keshi will see each other after at most $d$ days.

输出确保 AmShZ 和 Keshi 在至多 $d$ 天后相遇的最小可能整数 $d$。

In the first sample, it's enough for AmShZ to send the second type of message.

In the second sample, on the first day, AmShZ blocks the first road. So the only reachable city from city $1$ will be city $4$. Hence on the second day, AmShZ can tell Keshi to move and Keshi will arrive at AmShZ's house.

It's also possible for AmShZ to tell Keshi to move for two days.

在第一个样例中，AmShZ 只需发送第二种类型的消息即可。

在第二个样例中，第一天，AmShZ 封锁了第一条道路。因此，从城市 $1$ 出发唯一可达的城市是城市 $4$。于是第二天，AmShZ 可以告诉 Keshi 移动，Keshi 将到达 AmShZ 的住所。

此外，AmShZ 也可以连续两天都告诉 Keshi 移动。