Problem B
Commemorative Race

Photo by Pixabay

Filiberto is planning a race to celebrate the 2019 ICPC Mid-Central Regional. The racers compete by going down a mountain on a set of roads. As it would be dangerous to have cars speeding at each other in opposite directions, racers may only drive downhill on each road in a single direction. The endpoint of each road is called a station, and roads connect only at stations.

A path is a sequence of roads where the ending station of one road is the starting station of the next. Each racer must choose a path to race on. The length of a path is the number of roads in it.

The goal of this race is to stay on the course as long as possible – that is, to find a path of maximum length. Every racer knows the full layout of the stations and roads, and will choose some path of maximal length.

Filiberto is concerned about natural disasters (e.g., landslides) blocking off roads during the competition. If a road is blocked off, it may reduce the length of some paths of the race. This works as follows: say the road from station $u$ to station $v$ is blocked off. Then the racer will follow their path until station $u$, at which point they have to modify their path starting from station $u$, while still trying to maximize the length of their new path. As each racer knows the full map of the mountain, they will optimally re-route to maximize the length of their new path.

To understand the worst-case scenario, Filiberto wants to know the minimum length path that a winning racer would take if at most one of the roads is blocked off. This means that among all sets of maximum length paths that racers can choose and all possible roads that can be blocked off, what is the minimum length path that a racer may take after that road is blocked off and that path is at least as long as any other racers’ path (other racers are also effected by the same blocked road)?

Input

The first line of the input contains two integers $n$ and $m$ $(2 \le n \le 10^5, 1 \le m \le \min (n(n-1)/2, 10^6))$ – the number of stations and number of roads on the mountain. The next $m$ lines each contain two integers $u$ and $v$ $(1 \le u,v \le n, u \ne v)$ representing a one-way road from station $u$ to station $v$. It is guaranteed that there is at most one road between any pair of stations and there are no loops in the road graph (i.e. the input is a directed acyclic graph).

Output

Print a line with a single integer – the minimum length path that competitors can achieve if at most one of the roads is blocked off. That is, Filiberto wants to know the minimum longest time with the worst landslide location.

Sample Explanation

In the second sample, every racer will start from stations number $1$ or $7$. If the road $(2, 3)$ is blocked, then all racers will have to re-route at station $2$ towards station $5$.

In the third sample, the minimum path that could be taken happens by blocking the first road of the only path that racers can choose. Blocking any other road results in a longer path.

In the last sample there is only one maximum length path, but the best option is to block the road $(4, 5)$. If we block the road $(1, 4)$ the racers can re-route earlier and achieve a path of length $2$.

4 4
1 2
1 3
3 4
2 4

2

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

2

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

0

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

1