Distancia en la Red de Ciudades

Descripción

En un país en desarrollo, el ministerio de transporte ha construido una red de carreteras que conecta varias ciudades. Cada carretera conecta exactamente dos ciudades de manera bidireccional y tiene una longitud uniforme de 1 tramo (es decir, cada carretera equivale a una arista).

El ministerio desea analizar la conectividad del país. Se te otorgará la estructura de la red con N ciudades y E carreteras. Posteriormente, recibirás K consultas.

Cada consulta consta de dos ciudades, a y b. Tu tarea consiste en determinar si existe al menos una ruta entre la ciudad a y la ciudad b y, de ser así, indicar el número mínimo de carreteras (longitud del camino más corto) necesarias para viajar de a a b. Si no existe ningún camino entre ellas, se debe imprimir -1.

Entrada

En la primera línea, dos enteros N y E, que representan la cantidad de vértices (ciudades) y la cantidad de aristas (carreteras), respectivamente. Las ciudades están numeradas de 1 a N.

En cada una de las siguientes E líneas, dos enteros u_i y v_i, indicando que existe una arista no dirigida entre el vértice u_i y el vértice v_i.

En la siguiente línea, un entero K, que representa la cantidad de consultas.

En las siguientes K líneas, dos enteros a_j y b_j, representando los pares de vértices a consultar.

Salida

Para cada una de las K consultas, imprime en una nueva línea un entero con el número mínimo de aristas requeridas para ir del vértice a_j al vértice b_j.

Si no existe un camino entre a_j y b_j, imprime -1.

Si a_j = b_j, la respuesta debe ser 0.

Ejemplos

Ejemplo 1

Entrada

4 3
1 2
2 3
3 4
2
1 4
2 3

Salida

3
1

Explicación

• Consulta 1 (1 4): El camino entre el vértice 1 y el vértice 4 es 1 -> 2 -> 3 -> 4, el cual recorre un total de 3 aristas.
• Consulta 2 (2 3): Existe una arista directa entre el vértice 2 y el vértice 3, por lo que se requiere 1 arista.