Problem B
Commemorative Race

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
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
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
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
|
|
|
Sample |
Sample |
Sample |
Sample Input 1 | Sample Output 1 |
---|---|
4 4 1 2 1 3 3 4 2 4 |
2 |
Sample Input 2 | Sample Output 2 |
---|---|
7 6 1 2 2 3 2 5 6 3 7 2 3 4 |
2 |
Sample Input 3 | Sample Output 3 |
---|---|
7 5 1 2 2 3 3 4 5 6 6 7 |
0 |
Sample Input 4 | Sample Output 4 |
---|---|
6 5 1 2 1 4 2 3 4 5 5 6 |
1 |