题目描述

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

在远古时代，Nukos 仅居住在 $0$ 号岛屿上。然而，随着时间的推移，Nukos 已经扩散到了所有岛屿。每当一群 Nukos 穿过桥梁到达一个新岛屿时，它们就会经历进化，从而形成与前一个岛屿上不同的亚种。具体来说，对于所有 $0 \le j \le N - 1$ ，$j$ 号岛屿上的 Nukos 属于亚种 $s_j$ ，其中 $s_j$ 是从 $0$ 号岛屿到达 $j$ 号岛屿必须经过的最少桥梁数。比如， $0$ 号岛屿上的 Nukos 属于亚种 $0$ 。

你是一名旅行者，打算使用这些桥梁从 $A$ 号岛屿旅行到 $B$ 号岛屿。保证 $A \ne B$ 。当你在某个岛屿上时，你不可避免地会遇到居住在那里的 Nukos 亚种。由于每个亚种都有自己的习俗你需要适应，而适应不同的习俗可能会很麻烦，因此你的目标是选择一条路径，使得你遇到的不同 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 亚种的最小数量。

输入格式

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

输出格式

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

提示

样例

考虑以下函数调用。

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

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

:::align{center} :::

对于样例 $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 亚种。

:::align{center} :::

对于样例 $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$ 。

约束

• $2 \le N \le 5\ 000\ 000$ 。
• $1 \le M \le 5\ 000\ 000$ 。
• $0 \le A, B \le N - 1$ 。
• $A \ne B$
• 对于所有 $0 \le i \le M - 1$ ， $0 \le U[i], V[i] \le N - 1$ 。
• 对于所有 $0 \le i \le M - 1$ ， $U[i] \ne V[i]$ 。
• 对于所有 $0 \le i, j \le M - 1$ 和 $i \ne j$ ， $(U[i], V[i]) \ne (U[j], V[j])$ 且 $(U[i], V[i]) \ne (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$ ，评测程序会占用 $4500$ 毫秒时间限制中的 $1500$ 毫秒。