Una especie única y enigmática conocida como los Nuko habita un archipiélago en una parte remota del mundo. El archipiélago puede modelarse con $N$ islas, numeradas del $0$ al $N - 1$, conectadas por $M$ puentes. Cada puente $i$ une dos islas, $U[i]$ y $V[i]$, para todo $0 \leq i \leq M - 1$, en ambas direcciones. Es posible llegar a cualquier isla desde cualquier otra. Cada puente conecta dos islas distintas, y no hay dos puentes que conecten el mismo par de islas.

En la antigüedad, los Nuko habitaban únicamente la isla $0$. Sin embargo, ha pasado suficiente tiempo y los Nuko se han extendido a todas las islas. Cada vez que un grupo de Nuko cruza un puente hacia una nueva isla, experimentan una evolución, lo que resulta en una subespecie diferente en comparación con los de la isla anterior. Específicamente, para la isla $j$, para todo $0 \leq j \leq N - 1$, los Nuko son de la subespecie $s_j$, la cual es igual al número mínimo de puentes que uno debe cruzar para llegar a la isla $j$ desde la isla $0$. Por ejemplo, los Nuko en la isla $0$ son de la subespecie $0$.

Usted es un viajero que desea ir de la isla $A$ a la isla $B$ utilizando los puentes. Se garantiza que $A \neq B$. Cuando se encuentre en alguna isla, inevitablemente encontrará a la subespecie de Nuko que vive allí. Dado que cada subespecie tiene sus propias costumbres, y adaptarse a diferentes costumbres puede ser problemático, su objetivo es elegir un camino que minimice el número de subespecies de Nuko distintas que encuentre.

¿Puede determinar el número mínimo de subespecies de Nuko distintas que debe encontrar al viajar de la isla $A$ a la isla $B$?

Detalles de implementación

Debe implementar el siguiente procedimiento:

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

• $N$: el número de islas.
• $M$: el número de puentes.
• $A$: el punto de partida de su viaje.
• $B$: el punto de destino de su viaje.
• $U$, $V$: arreglos de longitud $M$ que describen los puentes.
• Este procedimiento debe devolver el número mínimo de subespecies de Nuko distintas que debe encontrar.

Restricciones

• $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$, para todo $0 \leq i \leq M - 1$.
• $U[i] \neq V[i]$, para todo $0 \leq i \leq M - 1$.
• $(U[i], V[i]) \neq (U[j], V[j])$ y $(U[i], V[i]) \neq (V[j], U[j])$, para todo $0 \leq i, j \leq M-1$ e $i \neq j$.
• Se garantiza que es posible llegar a cualquier isla desde cualquier otra.

Subtareas

1. (4 puntos) $A = 0$, $N \le 100\,000$, $M \le 100\,000$.
2. (4 puntos) $M = N - 1$, $N \le 100\,000$, $M \le 100\,000$.
3. (6 puntos) $N \le 300$, $M \le 300$.
4. (8 puntos) $N \le 4\,000$, $M \le 4\,000$.
5. (22 puntos) $N \le 4\,000$, $M \le 1\,000\,000$.
6. (14 puntos) $N \le 100\,000$, $M \le 100\,000$.
7. (5 puntos) $N \le 300\,000$, $M \le 300\,000$.
8. (5 puntos) $N \le 500\,000$, $M \le 500\,000$.
9. (32 puntos) Sin restricciones adicionales.

Nota: Para la subtarea 9, se garantiza que el evaluador por sí solo consumirá 1500ms del límite de tiempo de 4500ms.

Ejemplos

Considere las siguientes llamadas.

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

Las islas pueden ilustrarse como se muestra a continuación, donde el sombreado diferente representa diferentes subespecies de Nuko.

Para el ejemplo 1, el camino óptimo es $2-3-4$. Las subespecies de Nuko encontradas son $1$ y $2$. Por lo tanto, esta llamada debe devolver $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])

Las islas pueden ilustrarse como se muestra a continuación, donde el sombreado diferente representa diferentes subespecies de Nuko.

Para el ejemplo 2, el camino óptimo es $4-1-5-2-6-3-7$. Las subespecies de Nuko encontradas son $1$ y $2$. Por lo tanto, esta llamada debe devolver $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])

Para el ejemplo 3, el número mínimo de subespecies de Nuko distintas que debe encontrar al viajar de la isla $3$ a la isla $7$ es $3$. Por lo tanto, esta llamada debe devolver $3$.

Evaluador de muestra

Formato de entrada:

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

Formato de salida:

Un entero que representa el valor de retorno de min_distinct.