Problem Description

A unique and mysterious species called Nuko lives on an archipelago in a remote corner of the world. The archipelago can be modeled as $N$ islands, numbered from $0$ to $N - 1$, connected by $M$ bridges. For all $0 \le i \le M - 1$, bridge $i$ connects islands $U[i]$ and $V[i]$ in both directions. It is guaranteed that you can travel from any island to any other island. Each bridge connects two different islands, and no two bridges connect the same pair of islands.

In ancient times, Nukos lived only on island $0$. However, as time passed, Nukos spread to all islands. Whenever a group of Nukos crosses a bridge and reaches a new island, they evolve and form a subspecies different from the one on the previous island. More precisely, for all $0 \le j \le N - 1$, the Nukos on island $j$ belong to subspecies $s_j$, where $s_j$ is the minimum number of bridges that must be crossed to reach island $j$ from island $0$. For example, the Nukos on island $0$ belong to subspecies $0$.

You are a traveler and plan to use these bridges to travel from island $A$ to island $B$. It is guaranteed that $A \ne B$. When you are on an island, you will inevitably encounter the Nuko subspecies living there. Since each subspecies has its own customs that you need to adapt to, and adapting to different customs can be troublesome, your goal is to choose a path that minimizes the number of distinct Nuko subspecies you encounter.

Can you compute the minimum possible number of distinct Nuko subspecies you must encounter when traveling from island $A$ to island $B$?

Implementation Details

You need to implement the following function.

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

• $N$: the number of islands.
• $M$: the number of bridges.
• $A$: the starting island of your trip.
• $B$: the destination island of your trip.
• $U$, $V$: arrays of length $M$ describing the bridges.
• This function should return the minimum number of distinct Nuko subspecies you must encounter.

Input Format

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

Output Format

An integer, representing the return value of the min_distinct function.

Hint

Samples

Consider the following function call.

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

The diagram of the islands is as follows, where different shadings represent different Nuko subspecies.

:::align{center} :::

For sample $1$, the optimal path is $2 - 3 - 4$. The Nuko subspecies encountered are $1$ and $2$. Therefore, this call should return $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])

The diagram of the islands is as follows, where different shadings represent different Nuko subspecies.

:::align{center} :::

For sample $2$, the optimal path is $4 - 1 - 5 - 2 - 6 - 3 - 7$. The Nuko subspecies encountered are $1$ and $2$. Therefore, this call should return $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])

For sample $3$, when traveling from island $3$ to island $7$, the minimum number of distinct Nuko subspecies you must encounter is $3$. Therefore, this call should return $3$.

Constraints

• $2 \le N \le 5\ 000\ 000$.
• $1 \le M \le 5\ 000\ 000$.
• $0 \le A, B \le N - 1$.
• $A \ne B$.
• For all $0 \le i \le M - 1$, $0 \le U[i], V[i] \le N - 1$.
• For all $0 \le i \le M - 1$, $U[i] \ne V[i]$.
• For all $0 \le i, j \le M - 1$ and $i \ne j$, $(U[i], V[i]) \ne (U[j], V[j])$ and $(U[i], V[i]) \ne (V[j], U[j])$.
• It is guaranteed that you can travel from any island to any other island.

Subtasks

1. ($4$ points) $A = 0, N \le 100\ 000, M \le 100\ 000$.
2. ($4$ points) $M = N - 1, N \le 100\ 000, M \le 100\ 000$.
3. ($6$ points) $N \le 300, M \le 300$.
4. ($8$ points) $N \le 4\ 000, M \le 4\ 000$.
5. ($22$ points) $N \le 4\ 000, M \le 1\ 000\ 000$.
6. ($14$ points) $N \le 100\ 000, M \le 100\ 000$.
7. ($5$ points) $N \le 300\ 000, M \le 300\ 000$.
8. ($5$ points) $N \le 500\ 000, M \le 500\ 000$.
9. ($32$ points) No additional constraints.

Note: For subtask $9$, the judge will use $1500$ ms out of the $4500$ ms time limit.

Translated by ChatGPT 5