在世界偏遠地區的一個群島上，居住著一種獨特且神秘的物種，稱為 Nuko。該群島由 $N$ 個島嶼組成，編號從 $0$ 到 $N - 1$，並由 $M$ 座橋樑連接。每座橋樑 $i$ 連接兩個島嶼 $U[i]$ 和 $V[i]$（對於所有 $0 \leq i \leq M - 1$），且為雙向通行。從任何一個島嶼都可以到達其他任何島嶼。每座橋樑連接兩個不同的島嶼，且沒有兩座橋樑連接同一對島嶼。

在古代，Nuko 僅居住在島嶼 $0$。然而，經過漫長的歲月，Nuko 已經擴散到所有島嶼。每當一群 Nuko 跨越橋樑到達一個新島嶼時，牠們就會進化，產生與前一個島嶼不同的亞種。具體來說，對於島嶼 $j$（對於所有 $0 \leq j \leq N - 1$），其上的 Nuko 屬於亞種 $s_j$，該亞種編號等於從島嶼 $0$ 到達島嶼 $j$ 所需經過的最少橋樑數量。例如，島嶼 $0$ 上的 Nuko 屬於亞種 $0$。

你是一位旅行者，目標是利用橋樑從島嶼 $A$ 旅行到島嶼 $B$。保證 $A \neq B$。當你位於某個島嶼時，你不可避免地會遇到居住在那裡的 Nuko 亞種。由於每個亞種都有自己的習俗，而適應不同的習俗可能會很麻煩，因此你的目標是選擇一條路徑，使得你遇到的不同 Nuko 亞種數量最少。

你能否確定從島嶼 $A$ 旅行到島嶼 $B$ 時，必須遇到的不同 Nuko 亞種的最小數量？

實作細節

你應該實作以下函式：

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$ 的陣列，描述橋樑的連接關係。
• 此函式應回傳你必須遇到的不同 Nuko 亞種的最小數量。

資料範圍

• $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 \le U[i], V[i] \le N - 1$，對於所有 $0 \leq i \leq M - 1$
• $U[i] \neq V[i]$，對於所有 $0 \leq i \leq M - 1$
• $(U[i], V[i]) \neq (U[j], V[j])$ 且 $(U[i], V[i]) \neq (V[j], U[j])$，對於所有 $0 \leq i, j \leq M-1$ 且 $i \neq 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。

範例

輸入格式 1

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

輸出格式 1

2

說明

島嶼示意圖如下，不同的陰影代表不同的 Nuko 亞種：

對於範例 1，最佳路徑為 $2-3-4$。遇到的 Nuko 亞種為 $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

說明

島嶼示意圖如下，不同的陰影代表不同的 Nuko 亞種：

對於範例 2，最佳路徑為 $4-1-5-2-6-3-7$。遇到的 Nuko 亞種為 $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$ 時，必須遇到的不同 Nuko 亞種的最小數量為 $3$。因此，此呼叫應回傳 $3$。

範例評測程式

輸入格式：

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

輸出格式：

一個代表 min_distinct 回傳值的整數。