기념 경주

Filiberto는 2019 ICPC Mid-Central Regional을 기념하는 경주를 계획하고 있다. 참가자들은 산에 난 도로를 따라 내려가며 경주한다. 차들이 반대 방향에서 서로 마주 달리면 위험하므로, 각 도로는 한 방향으로만 내려갈 수 있다. 도로의 끝점을 지점(station)이라 부르며, 도로는 지점에서만 만난다.

경로(path)는 한 도로의 끝 지점이 다음 도로의 시작 지점인 도로들의 나열이다. 각 참가자는 경주할 경로를 하나 고른다. 경로의 길이는 그 경로에 포함된 도로의 수이다.

이 경주의 목표는 코스에서 최대한 오래 머무는 것, 즉 최대 길이의 경로를 찾는 것이다. 모든 참가자는 지점과 도로의 전체 배치를 알고 있으며, 최대 길이의 경로를 고른다.

Filiberto는 경주 중에 산사태 같은 자연재해로 도로가 막힐 것을 걱정한다. 도로가 막히면 일부 경로의 길이가 줄어들 수 있다. 지점 u에서 지점 v로 가는 도로가 막혔다고 하자. 참가자는 경로를 지점 u까지 따라간 뒤, u에서부터 나머지 경로를 다시 짜야 하며, 이때도 새 경로의 길이를 최대화하려고 한다. 모든 참가자가 산의 전체 지도를 알고 있으므로, 각자 최적으로 경로를 다시 잡아 새 경로의 길이를 최대로 만든다.

최악의 경우를 알아보기 위해 Filiberto는 도로가 최대 한 개 막혔을 때 우승할 참가자가 가는 경로의 최소 길이를 알고 싶어 한다. 참가자가 고를 수 있는 모든 최대 길이 경로 집합과 막힐 수 있는 모든 도로에 대해, 도로가 막힌 뒤 참가자가 갈 수 있는 경로 중 길이가 가장 짧은 것을 구한다. 단, 그 경로는 같은 도로에 영향을 받는 다른 참가자들의 경로보다 짧지 않아야 한다.

첫째 줄에 두 정수 n과 m이 주어진다 ($2 \le n \le 10^5$, $1 \le m \le \min(n(n-1)/2, 10^6)$). n은 지점의 수, m은 도로의 수이다. 다음 m개 줄에는 각각 두 정수 u와 v ($1 \le u, v \le n$, $u \ne v$)가 주어지며, 지점 u에서 지점 v로 가는 일방통행 도로가 있음을 뜻한다. 두 지점 사이에 도로는 최대 한 개이고, 고리는 없다. 입력은 방향 비순환 그래프이다.

도로가 최대 한 개 막혔을 때 참가자가 얻을 수 있는 경로 길이의 최소값을 한 줄에 출력한다. 즉, 최악의 산사태 위치에서 나올 수 있는 최장 경로 길이 중 최소값이다.

두 번째 예제에서 모든 참가자는 1번 또는 7번 지점에서 출발한다. 도로 (2, 3)이 막히면 모든 참가자는 2번 지점에서 5번 지점 방향으로 경로를 다시 잡아야 한다.

세 번째 예제에서 참가자가 고를 수 있는 경로는 하나뿐이다. 그 경로의 첫 번째 도로를 막으면 최소 길이가 된다. 다른 도로를 막으면 경로가 더 길어진다.

마지막 예제에서는 최대 길이 경로가 하나뿐이지만, 가장 좋은 선택은 도로 (4, 5)를 막는 것이다. 도로 (1, 4)를 막으면 참가자가 더 일찍 경로를 바꿔 길이 2의 경로를 얻는다.