En Byteland hay ~n~ ciudades, pero no hay carreteras que las conecten. Sin embargo, cada día se construirá una nueva carretera. Habrá un total de ~m~ carreteras.

Tu tarea es procesar ~q~ consultas del tipo: "¿Después de cuántos días podremos viajar de la ciudad ~a~ a la ciudad ~b~ por primera vez?".

Entrada

• La primera línea de entrada contiene tres números enteros: ~n, m~ y ~q~: el número de ciudades, carreteras y consultas. Las ciudades están numeradas del ~1~ al ~n~.
• A continuación, hay ~m~ líneas que describen las carreteras en el orden en que se construyen. Cada línea contiene dos números enteros: ~a~ y ~b~; siempre habrá una carretera entre las ciudades ~a~ y ~b~.
• Finalmente, hay ~q~ líneas que describen las consultas. Cada línea contiene dos números enteros: ~a~ y ~b~; queremos viajar de la ciudad ~a~ a la ciudad ~b~.

Salida

Para cada consulta, imprime el número de días, o -1 si nunca es posible.

Restricciones

• ~1 \leq n, m, q \leq 2 \cdot 10^5~
• ~1 \leq a,b \leq n~

Ejemplo de Entrada

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

Ejemplo de Salida

2
-1
4