누코(Nuko)라고 불리는 독특하고 신비로운 종이 세계의 외딴 지역에 있는 군도에 서식하고 있습니다. 이 군도는 $0$부터 $N - 1$까지 번호가 매겨진 $N$개의 섬과 이들을 잇는 $M$개의 다리로 모델링할 수 있습니다. 각 다리 $i$는 $0 \leq i \leq M - 1$에 대해 두 섬 $U[i]$와 $V[i]$를 양방향으로 연결합니다. 모든 섬은 다른 모든 섬에서 도달할 수 있습니다. 각 다리는 서로 다른 두 섬을 연결하며, 같은 두 섬을 연결하는 다리는 두 개 이상 존재하지 않습니다.

고대에는 누코들이 섬 $0$에만 서식했습니다. 하지만 충분한 시간이 흘러 누코들은 모든 섬으로 퍼져 나갔습니다. 누코 무리가 다리를 건너 새로운 섬으로 이동할 때마다 그들은 진화하여 이전 섬의 누코들과는 다른 아종이 됩니다. 구체적으로, 모든 $0 \leq j \leq N - 1$에 대해 섬 $j$에 사는 누코는 아종 $s_j$에 속하며, $s_j$는 섬 $0$에서 섬 $j$까지 도달하기 위해 건너야 하는 최소 다리 개수와 같습니다. 예를 들어, 섬 $0$에 있는 누코는 아종 $0$입니다.

당신은 다리를 이용하여 섬 $A$에서 섬 $B$로 여행하려는 여행자입니다. $A \neq B$임이 보장됩니다. 어떤 섬에 있을 때, 당신은 그곳에 사는 누코의 아종을 필연적으로 마주하게 됩니다. 각 아종은 고유한 관습을 가지고 있고, 다른 관습에 적응하는 것은 번거로울 수 있기 때문에, 당신의 목표는 마주치는 서로 다른 누코 아종의 수를 최소화하는 경로를 선택하는 것입니다.

섬 $A$에서 섬 $B$로 여행할 때 마주쳐야 하는 서로 다른 누코 아종의 최소 개수를 구할 수 있습니까?

구현 세부사항

다음 프로시저를 구현해야 합니다.

int min_distinct(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V)

• $N$: 섬의 개수.
• $M$: 다리의 개수.
• $A$: 여행의 시작점.
• $B$: 여행의 도착점.
• $U$, $V$: 다리를 설명하는 길이 $M$의 배열.
• 이 프로시저는 마주쳐야 하는 서로 다른 누코 아종의 최소 개수를 반환해야 합니다.

제한

• $2 \le N \le 5\,000\,000$.
• $1 \le M \le 5\,000\,000$.
• $0 \le A, B \le N - 1$.
• $A \neq B$.
• 모든 $0 \leq i \leq M - 1$에 대해 $0 \le U[i], V[i] \le N - 1$.
• 모든 $0 \le i \leq M - 1$에 대해 $U[i] \neq V[i]$.
• 모든 $0 \le i, j \le M-1$ ($i \neq j$)에 대해 $(U[i], V[i]) \neq (U[j], V[j])$ 이고 $(U[i], V[i]) \neq (V[j], U[j])$.
• 모든 섬은 다른 모든 섬에서 도달할 수 있음이 보장됩니다.

서브태스크

1. (4점) $A = 0$, $N \le 100\,000$, $M \le 100\,000$.
2. (4점) $M = N - 1$, $N \le 100\,000$, $M \le 100\,000$.
3. (6점) $N \le 300$, $M \le 300$.
4. (8점) $N \le 4\,000$, $M \le 4\,000$.
5. (22점) $N \le 4\,000$, $M \le 1\,000\,000$.
6. (14점) $N \le 100\,000$, $M \le 100\,000$.
7. (5점) $N \le 300\,000$, $M \le 300\,000$.
8. (5점) $N \le 500\,000$, $M \le 500\,000$.
9. (32점) 추가 제한 없음.

참고: 서브태스크 9의 경우, 채점기 자체에서 4500ms의 시간 제한 중 1500ms를 소모하는 것으로 간주합니다.

예제

다음 호출들을 고려하십시오.

min_distinct(5, 5, 2, 4, [0, 1, 2, 3, 4], [1, 2, 3, 4, 0])

섬들은 아래와 같이 나타낼 수 있으며, 서로 다른 음영은 서로 다른 누코 아종을 나타냅니다.

출력 1

2

참고

예제 1에서 최적의 경로는 $2-3-4$입니다. 마주치는 누코 아종은 $1$과 $2$입니다. 따라서 이 호출은 $2$를 반환해야 합니다.

입력 2

min_distinct(8, 9, 4, 7, [0, 0, 0, 1, 1, 2, 2, 6, 7], [1, 2, 3, 4, 5, 5, 6, 3, 3])

섬들은 아래와 같이 나타낼 수 있으며, 서로 다른 음영은 서로 다른 누코 아종을 나타냅니다.

출력 2

2

참고

예제 2에서 최적의 경로는 $4-1-5-2-6-3-7$입니다. 마주치는 누코 아종은 $1$과 $2$입니다. 따라서 이 호출은 $2$를 반환해야 합니다.

입력 3

min_distinct(15, 17, 3, 7,
              [0, 1, 2, 3, 4, 13, 12, 12, 11, 10, 10, 9, 8, 7, 6, 8, 0],
              [1, 2, 3, 4, 13, 12, 1, 11, 10, 9, 5, 8, 7, 6, 5, 14, 14])

출력 3

3

참고

예제 3에서 섬 $3$에서 섬 $7$로 여행할 때 마주쳐야 하는 서로 다른 누코 아종의 최소 개수는 $3$입니다. 따라서 이 호출은 $3$을 반환해야 합니다.

예제 채점기

입력 형식:

N M A B
U[0] V[0]
U[1] V[1]
...
U[M - 1] V[M - 1]

출력 형식:

min_distinct의 반환 값을 나타내는 정수 하나.