Unikalny i enigmatyczny gatunek znany jako Nuko zamieszkuje archipelag w odległej części świata. Archipelag można modelować za pomocą $N$ wysp, ponumerowanych od $0$ do $N - 1$, połączonych $M$ mostami. Każdy most $i$ łączy dwie wyspy, $U[i]$ oraz $V[i]$, dla wszystkich $0 \leq i \leq M - 1$, w obu kierunkach. Możliwe jest dotarcie z każdej wyspy na każdą inną. Każdy most łączy dwie różne wyspy i żadne dwa mosty nie łączą tej samej pary wysp.

W dawnych czasach Nuko zamieszkiwały wyłącznie wyspę $0$. Jednakże minęło wystarczająco dużo czasu i Nuko rozprzestrzeniły się na wszystkie wyspy. Ilekroć grupa Nuko przekracza most na nową wyspę, przechodzi ewolucję, co skutkuje powstaniem podgatunku różniącego się od tych na poprzedniej wyspie. Konkretnie, dla wyspy $j$, dla wszystkich $0 \leq j \leq N - 1$, Nuko należą do podgatunku $s_j$, który jest równy najmniejszej liczbie mostów, które trzeba przekroczyć, aby dotrzeć na wyspę $j$ z wyspy $0$. Na przykład Nuko na wyspie $0$ należą do podgatunku $0$.

Jesteś podróżnikiem, którego celem jest przebycie drogi z wyspy $A$ do $B$ przy użyciu mostów. Gwarantuje się, że $A \neq B$. Będąc na dowolnej wyspie, nieuchronnie napotkasz podgatunek Nuko tam żyjący. Ponieważ każdy podgatunek ma swoje własne zwyczaje, a przystosowanie się do różnych zwyczajów może być kłopotliwe, Twoim celem jest wybranie takiej ścieżki, która zminimalizuje liczbę różnych napotkanych podgatunków Nuko.

Czy potrafisz wyznaczyć minimalną liczbę różnych podgatunków Nuko, które musisz napotkać podczas podróży z wyspy $A$ do $B$?

Szczegóły implementacji

Powinieneś zaimplementować następującą procedurę:

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

• $N$: liczba wysp.
• $M$: liczba mostów.
• $A$: punkt startowy Twojej podróży.
• $B$: punkt końcowy Twojej podróży.
• $U$, $V$: tablice o długości $M$ opisujące mosty.
• Ta procedura powinna zwrócić minimalną liczbę różnych podgatunków Nuko, które musisz napotkać.

Ograniczenia

• $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$, dla wszystkich $0 \leq i \leq M - 1$.
• $U[i] \neq V[i]$, dla wszystkich $0 \le i \le M - 1$.
• $(U[i], V[i]) \neq (U[j], V[j])$ oraz $(U[i], V[i]) \neq (V[j], U[j])$, dla wszystkich $0 \le i, j \le M-1$ oraz $i \neq j$.
• Gwarantuje się, że możliwe jest dotarcie z każdej wyspy na każdą inną.

Podzadania

1. (4 punkty) $A = 0$, $N \le 100\,000$, $M \le 100\,000$.
2. (4 punkty) $M = N - 1$, $N \le 100\,000$, $M \le 100\,000$.
3. (6 punktów) $N \le 300$, $M \le 300$.
4. (8 punktów) $N \le 4\,000$, $M \le 4\,000$.
5. (22 punkty) $N \le 4\,000$, $M \le 1\,000\,000$.
6. (14 punktów) $N \le 100\,000$, $M \le 100\,000$.
7. (5 punktów) $N \le 300\,000$, $M \le 300\,000$.
8. (5 punktów) $N \le 500\,000$, $M \le 500\,000$.
9. (32 punkty) Brak dodatkowych ograniczeń.

Uwagi: W przypadku podzadania 9, sam system sprawdzający zużywa 1500ms z limitu czasu wynoszącego 4500ms.

Przykład

Wejście 1

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

Wyjście 1

2

Uwagi

Wyspy można zilustrować poniżej, gdzie różne cieniowanie reprezentuje różne podgatunki Nuko.

Dla przykładu 1, optymalna ścieżka to $2-3-4$. Napotkane podgatunki Nuko to $1$ oraz $2$.

Wejście 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])

Wyjście 2

2

Uwagi

Wyspy można zilustrować poniżej, gdzie różne cieniowanie reprezentuje różne podgatunki Nuko.

Dla przykładu 2, optymalna ścieżka to $4-1-5-2-6-3-7$. Napotkane podgatunki Nuko to $1$ oraz $2$.

Wejście 3

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

Wyjście 3

3

Przykładowy system sprawdzający

Format wejścia:

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

Format wyjścia:

Liczba całkowita reprezentująca wartość zwracaną przez min_distinct.