해류

버려진 집의 아트리움에 잘 숨겨진 곳에서, Bonn시의 가장 철저히 지켜진 비밀을 밝혀 주는 고대의 책을 발견했다. 도시 깊은 지하에는 $M$개의 수로로 연결된 $N$개의 동굴로 이루어진 동굴계가 있다. 각 수로 안에는 배를 수로를 따라 빠르게 운반할 수 있는 단방향 마법 해류가 흐른다. 현재 동굴계에는 정확히 하나의 출구가 있으며, 동굴 $N-1$에 있다.

당신은 이 발견에 매우 흥분하여 어서 동굴을 탐험하고 싶다! 하지만 이 동굴계에는 초대받지 않은 방문객을 골탕 먹이는 것을 좋아하는 트롤이 살고 있다. 트롤은 제한된 마력을 지니고 있으며, 방문 중 최대 한 번 이를 사용하여 동굴계를 변경하고 당신이 출구에 도달하기 어렵게 만들 수 있다.

동굴계 방문은 일련의 라운드로 이루어진다. 각 라운드는 다음과 같이 진행된다.

• 먼저 트롤은 자신의 마력을 사용할지 말지 선택한다. 마력을 사용하면 주문은 다음 작업을 모두 수행한다.

• 모든 수로에 흐르는 마법 해류의 방향을 뒤집는다. 즉, $a \rightarrow b$는 즉시 $b \rightarrow a$로 바뀐다.

• 동굴 $N-1$의 출구를 닫는다. 그리고

• 동굴 $0$에 새로운 출구를 연다.

• 그다음 당신은 현재 동굴에서 흘러나가는 마법 해류 하나를 선택하고, 배를 타고 다른 동굴로 이동한다. 편의상 배를 한 번 이용하는 것을 ``이동''이라고 부른다.

또한 출구와 같은 동굴에 있게 되는 즉시 출구를 이용해 동굴계를 떠난다. 이는 라운드 도중에도 일어날 수 있음에 유의하라. 예를 들어 당신이 동굴 $0$에 있을 때 트롤이 자신의 마력을 사용하기로 한 경우이다.

당신의 목표는 EGOI의 폐막식에 늦지 않도록 최대한 빨리 동굴계를 떠나는 것이다. 트롤의 목표는 정확히 그 반대이다. 트롤은 당신을 자신의 동굴에 최대한 오래 붙잡아 두고 싶어 한다. 트롤은 항상 당신의 위치를 알고 있으며, 자신의 목표를 가장 잘 달성하도록 마력을 사용할 순간을 선택한다.

각 동굴 $c$ ($0 \leq c \leq N-2$)에 대해, 동굴 $c$에서 시작하는 상황을 각각 따로 생각하자. 각 상황에 대해, 트롤이 언제 자신의 마력을 사용하기로 선택하더라도 동굴 $c$에서 출발해 확실히 출구에 도달할 수 있는 최소 이동 횟수를 구하여라.

주문이 사용되지 않는다고 가정하면, 동굴 $0$에서 모든 동굴에 도달할 수 있으며 모든 동굴에서 동굴 $N-1$에 도달할 수 있다.

제약 조건과 채점

• $2 \leq N \leq 200\,000$.

• $1 \leq M \leq 500\,000$.

• $0 \leq a_i, b_i \leq N-1$ 그리고 $a_i \neq b_i$.

• 방향이 뒤집히기 전에는 동굴 $0$에서 모든 동굴에 도달할 수 있고, 모든 동굴에서 동굴 $N-1$에 도달할 수 있다.

당신의 풀이는 각각 일정한 점수가 배정된 여러 테스트 그룹으로 평가된다. 각 테스트 그룹은 여러 테스트 케이스를 포함한다. 테스트 그룹의 점수를 얻으려면 그 테스트 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제한

1 | 12 | 모든 $i$에 대해 $M=N-1$, $a_i = i$ 그리고 $b_i = i + 1$이다. 다시 말해, 동굴계는 경로 $0 \rightarrow 1 \rightarrow 2 \rightarrow \ldots \rightarrow N-1$를 이룬다

2 | 15 | 각 $0 \le i \le N-2$에 대해 동굴 $i$에서 동굴 $N-1$로 직접 이어지는 수로가 있다. 추가 수로가 있을 수도 있음에 유의하라.

3 | 20 | $N, M \leq 2\,000$

4 | 29 | 어떤 동굴이든 떠난 뒤에는 그 동굴로 다시 이동할 수 없다(방향이 뒤집히기 전까지). 다시 말해, 수로들은 방향 비순환 그래프를 이룬다.

5 | 24 | 추가 제약 조건 없음

예제

첫 번째 예제에서는 동굴 1에서 시작하는 경우를 생각하자. 방향이 언제 뒤집힐지 모르므로 동굴 4의 출구를 향해 이동하기 시작해야 한다. 동굴 2 또는 동굴 3을 거쳐 갈 수 있다. 여기서는 동굴 3을 거치는 편이 더 낫다. 그곳에 있는 동안 방향이 뒤집히면, 이제 동굴 3에서 동굴 0로 직접 이동하는 데 사용할 수 있는 수로가 생기며, 그곳에서 동굴계를 빠져나갈 수 있기 때문이다.

더 정확히 말하면, 트롤이 자신의 마력을 사용하기로 결정할 시점에는 다음 세 가지 가능성만 있다.

• 당신이 동굴 1에 있을 때 트롤이 즉시 자신의 마력을 사용하면, 그다음 동굴 1에서 동굴 0로 직접 이동하여 빠져나갈 수 있다.

• 당신이 동굴 1에서 동굴 3로 이동한 뒤 트롤이 자신의 마력을 사용하면, 그다음 동굴 3에서 동굴 0로 직접 이동하여 빠져나갈 수 있다.

• 트롤이 그 두 상황 중 어느 상황에서도 자신의 마력을 사용하지 않기로 하면, 동굴 3에서 동굴 4로 이동하여 빠져나간다.

첫 번째 경우에는 한 번만 이동하면 되었고, 나머지 각 경우에는 두 번 이동했다. 따라서 이 경우의 답은 $\max(1,2,2) = 2$이다.

동굴 1에서 동굴 2로 이동하기로 선택하면 트롤이 당신에게 세 번 이동하도록 강제할 수 있음에 유의하라.

첫 번째와 두 번째 예제는 테스트 그룹 3, 4 그리고 5의 제약 조건을 만족한다. 세 번째 예제는 모든 테스트 그룹의 제약 조건을 만족한다. 네 번째 예제는 테스트 그룹 3과 5의 제약 조건을 만족하며, 아래에 그림으로 나타나 있다.

입력의 첫 번째 줄에는 두 정수 $N$와 $M$가 주어진다. 여기서 $N$는 동굴의 수이고 $M$은 수로의 수이다. 이어지는 $M$개의 줄에는 각각 두 정수 $a_i$와 $b_i$가 주어지며, 현재 동굴 $a_i$에서 동굴 $b_i$로 이동하는 데 사용할 수 있는 수로를 나타낸다. 동굴과 자기 자신을 연결하는 수로는 없다. 각 동굴 쌍에 대해 각 방향으로 최대 하나의 수로가 있다.

$N-1$개의 정수를 한 줄에 출력한다. 이때 $i$번째 정수 $0 \leq i \leq N-2$는 동굴 $i$에서 시작할 때 확실히 출구에 도달할 수 있는 최소 이동 횟수이다.

동굴 $N - 1$에서는 즉시 빠져나가므로 이 동굴에 대한 시간은 출력하지 않음에 유의하라.