Commemorative Race

Time limit2sMemory limit512 MB

Summary

Given a DAG of one-way roads, find the minimum over all single blocked roads of the longest path length after racers re-route optimally from the blocked point.

Level: Medium6 of 10
Topics: Dynamic programming, Topological sort, Graph
Solved: No attempts yet

Problem

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. Cars speeding at each other in opposite directions would be dangerous, so each road may only be driven downhill in one 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 chooses a path to race on. The length of a path is the number of roads in it.

The goal of the 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 chooses a path of maximal length.

Filiberto is concerned about natural disasters, such as landslides, blocking roads during the competition. If a road is blocked, some paths may become shorter. Suppose the road from station u to station v is blocked. The racer follows their path up to station u, then modifies the rest of the path from u, still trying to maximize its length. Since each racer knows the full map of the mountain, each one re-routes optimally to maximize the length of the new path.

To study the worst case, Filiberto wants the minimum length of the path that a winning racer takes when at most one road is blocked. Among all sets of maximum length paths that racers can choose and all roads that can be blocked, find the minimum length of a path a racer may take after the blocked road, where that path is at least as long as the paths of the other racers, who are affected by the same blocked road.

Input

The first line 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 the number of roads. Each of the next m lines contains two integers u and v ( $1 \le u, v \le n$ , $u \ne v$ ), meaning there is a one-way road from station u to station v. There is at most one road between any pair of stations, and there are no loops. The input is a directed acyclic graph.

Output

Print one integer, the minimum length path that competitors can achieve if at most one road is blocked. In other words, print the minimum longest path length under the worst landslide location.

Hints

In the second sample, every racer starts from station 1 or station 7. If the road (2, 3) is blocked, all racers must re-route at station 2 toward station 5.

In the third sample, the only path racers can choose is one path. Blocking its first road gives the minimum path length. Blocking any other road gives a longer path.

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

Examples4

Example 1
Input
```
4 4
1 2
1 3
3 4
2 4
```
Expected output
```
2
```
Example 2
Input
```
7 6
1 2
2 3
2 5
6 3
7 2
3 4
```
Expected output
```
2
```
Example 3
Input
```
7 5
1 2
2 3
3 4
5 6
6 7
```
Expected output
```
0
```
Example 4
Input
```
6 5
1 2
1 4
2 3
4 5
5 6
```
Expected output
```
1
```