Description

A unique and enigmatic species known as the Nuko inhabits an archipelago in a remote part of the world. The archipelago can be modelled with $N$ islands, numbered from $0$ to $N - 1$, connected by $M$ bridges. Each bridge $i$ links two islands, $U[i]$ and $V[i]$, for all $0 \leq i \leq M - 1$, in both directions. It is possible to reach any island from any other island. Each bridge connects two distinct islands, and no two bridges connect the same pair of islands.

In ancient times, Nukos solely inhabited island $0$. However, enough time has passed, and the Nukos have spread to all islands. Whenever a group of Nukos crosses a bridge to a new island, they undergo evolution, resulting in a different subspecies compared to those on the previous island. Specifically, for island $j$, for all $0 \leq j \leq N - 1$, the Nukos are of subspecies $s_j$, which equals the smallest number of bridges one must cross to reach island $j$ from island $0$. For instance, Nukos on island $0$ are of subspecies $0$.

You are a traveller aiming to journey from islands $A$ to $B$ using the bridges. It is guaranteed that $A \neq B$. When you are on some island, you will inevitably encounter the subspecies of Nukos living there. Since each subspecies has its own customs, and adapting to different customs can be troublesome, your goal is to choose a path that minimises the number of distinct Nuko subspecies you encounter.

Can you determine the minimum number of distinct Nuko subspecies you have to encounter when travelling from island $A$ to $B$?

Implementation Details

You should implement the following procedure.

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 point of your journey.
• $B$: the ending point of your journey.
• $U$, $V$: arrays of length $M$ describing the bridges.
• This procedure should return the minimum number of distinct Nuko subspecies that you have to encounter.

Constraints

• $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$, for all $0 \leq i \leq M - 1$.
• $U[i] \neq V[i]$, for all $0 \le i \le M - 1$.
• $(U[i], V[i]) \neq (U[j], V[j])$ and $(U[i], V[i]) \neq (V[j], U[j])$, for all $0 \le i, j \le M-1$ and $i \neq j$.
• It is guaranteed that it is possible to reach any island from 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 grader alone is guaranteed to consume 1500ms of the 4500ms time limit.

Example

Consider the following calls.

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

The islands can be illustrated as below, with different shading representing different Nuko subspecies.

For example 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 islands can be illustrated as below, with different shading representing different Nuko subspecies.

For example 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 example 3, the minimum number of distinct Nuko subspecies you have to encounter when travelling from island $3$ to island $7$ is $3$. Therefore, this call should return $3$.

Sample Grader

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 min_distinct.