Уникальный и загадочный вид существ, известный как Нуко, обитает на архипелаге в отдаленной части мира. Архипелаг можно представить как $N$ островов, пронумерованных от $0$ до $N - 1$, соединенных $M$ мостами. Каждый мост $i$ соединяет два острова, $U[i]$ и $V[i]$, для всех $0 \leq i \leq M - 1$, в обоих направлениях. С любого острова можно добраться до любого другого. Каждый мост соединяет два различных острова, и никакие два моста не соединяют одну и ту же пару островов.

В древние времена Нуко обитали только на острове $0$. Однако прошло достаточно времени, и Нуко распространились по всем островам. Всякий раз, когда группа Нуко переходит по мосту на новый остров, они эволюционируют, становясь другим подвидом по сравнению с теми, что были на предыдущем острове. В частности, для острова $j$, где $0 \leq j \leq N - 1$, Нуко относятся к подвиду $s_j$, который равен минимальному количеству мостов, которые нужно пересечь, чтобы добраться до острова $j$ от острова $0$. Например, Нуко на острове $0$ относятся к подвиду $0$.

Вы — путешественник, стремящийся добраться от острова $A$ до острова $B$, используя мосты. Гарантируется, что $A \neq B$. Находясь на любом острове, вы неизбежно встретитесь с подвидом Нуко, живущим там. Поскольку у каждого подвида свои обычаи, а адаптация к разным обычаям может быть затруднительной, ваша цель — выбрать путь, который минимизирует количество различных подвидов Нуко, встреченных вами.

Можете ли вы определить минимальное количество различных подвидов Нуко, которые вам придется встретить при путешествии от острова $A$ до острова $B$?

Детали реализации

Вам необходимо реализовать следующую функцию:

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$, описывающие мосты.
• Эта функция должна возвращать минимальное количество различных подвидов Нуко, которые вам придется встретить.

Ограничения

• $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$ для всех $0 \leq i \leq M - 1$.
• $U[i] \neq V[i]$ для всех $0 \leq i \leq M - 1$.
• $(U[i], V[i]) \neq (U[j], V[j])$ и $(U[i], V[i]) \neq (V[j], U[j])$ для всех $0 \leq i, j \leq M-1$ и $i \neq 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 гарантируется, что только проверяющая система (grader) потребляет 1500 мс из 4500 мс лимита времени.

Примеры

Рассмотрим следующие вызовы.

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

Острова можно проиллюстрировать следующим образом, где разная штриховка представляет разные подвиды Нуко.

Для примера 1 оптимальный путь — $2-3-4$. Встреченные подвиды Нуко: $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])

Острова можно проиллюстрировать следующим образом, где разная штриховка представляет разные подвиды Нуко.

Для примера 2 оптимальный путь — $4-1-5-2-6-3-7$. Встреченные подвиды Нуко: $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$, равно $3$. Таким образом, функция должна вернуть $3$.

Пример проверяющей системы

Формат входных данных:

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

Формат выходных данных:

Целое число, представляющее возвращаемое значение min_distinct.