一种被称为 Nuko 的独特而神秘的物种居住在世界偏远地区的一个群岛上。该群岛可以建模为 $N$ 个岛屿，编号从 $0$ 到 $N - 1$，由 $M$ 座桥梁连接。对于所有 $0 \leq i \leq M - 1$，每座桥 $i$ 双向连接两个岛屿 $U[i]$ 和 $V[i]$。从任何一个岛屿都可以到达其他任何岛屿。每座桥连接两个不同的岛屿，且没有两座桥连接同一对岛屿。

在古代，Nuko 仅居住在岛屿 $0$ 上。然而，随着时间的推移，Nuko 已经扩散到所有岛屿。每当一群 Nuko 穿过一座桥到达一个新的岛屿时，它们就会发生进化，从而产生与前一个岛屿上的 Nuko 不同的亚种。具体来说，对于所有 $0 \leq j \leq N - 1$，岛屿 $j$ 上的 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。

样例

考虑以下调用：

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

岛屿示意图如下，不同的阴影代表不同的 Nuko 亚种：

对于样例 1，最优路径是 $2-3-4$。遇到的 Nuko 亚种为 $1$ 和 $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])

岛屿示意图如下，不同的阴影代表不同的 Nuko 亚种：

对于样例 2，最优路径是 $4-1-5-2-6-3-7$。遇到的 Nuko 亚种为 $1$ 和 $2$。因此，该调用应返回 $2$。

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$ 到岛屿 $7$ 旅行时必须遇到的不同 Nuko 亚种的最小数量为 $3$。因此，该调用应返回 $3$。

样例评测程序

输入格式：

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

输出格式：

一个表示 min_distinct 返回值的整数。