#216698. [SEATST 2026] 麻烦的旅程 / Troublesome Trip

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

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

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

你能计算出在从 号岛屿旅行到 号岛屿时，你必须遇到的最少的不同 Nuko 亚种数量吗？

实现详情

你需要实现以下函数。

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

• ：岛屿的数量。
• ：桥梁的数量。
• ：你旅行的起点。
• ：你旅行的终点。
• 、 ：长度为 的数组，描述这些桥梁。
• 此函数应返回你必须遇到的不同 Nuko 亚种的最小数量。

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

样例

考虑以下函数调用。

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

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

:::align{center} :::

对于样例 ，最优路径是 。遇到的 Nuko 亚种有 和 。因此，该调用应返回 。

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} :::

对于样例 ，最优路径是 。遇到的 Nuko 亚种有 和 。因此，该调用应返回 。

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])

对于样例 ，从 号岛屿旅行到 号岛屿时，你必须遇到的不同 Nuko 亚种的最少数量为 。因此，该调用应返回 。

约束

• 。
• 。
• 。
• 对于所有 ， 。
• 对于所有 ， 。
• 对于所有 和 ， 且 。
• 保证可以从任意一个岛屿到达其他任意岛屿。

子任务

1. ( 分) 。
2. ( 分) 。
3. ( 分) 。
4. ( 分) 。
5. ( 分) 。
6. ( 分) 。
7. ( 分) 。
8. ( 分) 。
9. ( 分) 没有额外的约束。

注意： 对于子任务 ，评测程序会占用 毫秒时间限制中的 毫秒。