Problema

Te has adentrado por error en una gran mansión. Esta mansión tiene una estructura en la que habitaciones cuadradas están dispuestas en forma de cuadrícula en las direcciones este-oeste y norte-sur, con $M$ columnas en la dirección este-oeste y $N$ filas en la dirección norte-sur, haciendo un total de $M \times N$ habitaciones. La habitación situada en la columna $x$ desde el oeste ($1 \le x \le M$) y en la fila $y$ desde el sur ($1 \le y \le N$) se representa por $(x, y)$.

Cada par de $2$ habitaciones adyacentes en dirección este, oeste, sur o norte está conectado mediante una puerta situada en el centro de la pared. Cada puerta se encuentra o bien cerrada (intransitable) o bien abierta (transitable). Cuando una puerta está abierta, se tarda $1$ minuto en desplazarse entre los centros de esas habitaciones. Además, en el centro de algunas habitaciones hay un interruptor; si mantienes pulsado un interruptor durante $1$ minuto, el estado de apertura/cierre de todas las puertas de la mansión se invierte.

Ahora mismo, todas las puertas que conectan $2$ habitaciones adyacentes en dirección este-oeste están cerradas, y todas las puertas que conectan $2$ habitaciones adyacentes en dirección norte-sur están abiertas. Actualmente te encuentras en el centro de la habitación $(1, 1)$, y quieres desplazarte hasta el centro de la habitación $(M, N)$ en el menor tiempo posible.

Tarea

Dados el tamaño $M, N$ de la mansión y las posiciones $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ de las $K$ habitaciones que tienen interruptor, escribe un programa para hallar el número mínimo de minutos necesarios para desplazarse desde el centro de la habitación $(1, 1)$ hasta el centro de la habitación $(M, N)$, empezando desde el estado en que todas las puertas que conectan $2$ habitaciones adyacentes en dirección este-oeste están cerradas y todas las puertas que conectan $2$ habitaciones adyacentes en dirección norte-sur están abiertas. Sin embargo, si es imposible llegar a la habitación $(M, N)$, indícalo.

Restricciones

• $2 \le M \le 100000$: el número de habitaciones de la mansión en la dirección este-oeste.
• $2 \le N \le 100000$: el número de habitaciones de la mansión en la dirección norte-sur.
• $1 \le K \le 200000$: el número de habitaciones con interruptor.
• $1 \le X_i \le M$: la posición en la dirección este-oeste de una habitación con interruptor.
• $1 \le Y_i \le N$: la posición en la dirección norte-sur de una habitación con interruptor.

Entrada

Lee los siguientes datos desde la entrada estándar.

• En la línea $1$ están escritos los enteros $M, N, K$ separados por espacios. $M$ representa el número de habitaciones de la mansión en la dirección este-oeste, $N$ representa el número de habitaciones de la mansión en la dirección norte-sur, y $K$ representa el número de habitaciones con interruptor.
• En la $i$-ésima línea ($1 \le i \le K$) de las siguientes $K$ líneas están escritos los enteros $X_i, Y_i$ separados por un espacio. Esto indica que hay un interruptor en el centro de la habitación $(X_i, Y_i)$. Los $K$ pares $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ son todos distintos entre sí.

Salida

Imprime en $1$ línea en la salida estándar el entero que representa el número mínimo de minutos necesarios para el desplazamiento. Sin embargo, si no es posible llegar a la habitación $(M, N)$, imprime en su lugar el entero $-1$.

Criterios de calificación

• Para el $20\%$ de la puntuación total, se cumple que $M \le 1000$ y $N \le 1000$.
• Para el $30\%$ de la puntuación total, se cumple que $K \le 2000$.
• Para el $50\%$ de la puntuación total, se cumple al menos una de estas $2$ condiciones. Además, no hay datos de prueba que cumplan ambas de estas $2$ condiciones simultáneamente.

Ejemplo 1

Entrada

3 2 1
1 2

Salida

4

Explicación

En este ejemplo, puedes desplazarte desde el centro de la habitación $(1, 1)$ hasta el centro de la habitación $(3, 2)$ en $4$ minutos mediante las siguientes acciones, siendo este el tiempo mínimo:

• Desplazarse al centro de la habitación $(1, 2)$.
• Pulsar el interruptor en el centro de la habitación $(1, 2)$.
• Desplazarse al centro de la habitación $(2, 2)$.
• Desplazarse al centro de la habitación $(3, 2)$.

El estado de la mansión durante este proceso se muestra en la siguiente figura. En la figura, la derecha es el este, arriba es el norte, la marca $\times$ representa tu posición y la marca $\bigcirc$ representa un interruptor.

Ejemplo 2

Entrada

3 2 1
2 1

Salida

-1

Explicación

En este ejemplo, no puedes llegar a la habitación $(3, 2)$.

Ejemplo 3

Entrada

8 9 15
3 1
3 2
3 7
3 8
1 1
4 5
4 3
5 6
5 8
6 3
6 2
7 5
8 9
8 6
8 5

Salida

25

Explicación

En este ejemplo, el estado inicial de la mansión es como se muestra en la siguiente figura. Ten en cuenta que también puede haber un interruptor en el centro de la habitación $(1, 1)$ o de la habitación $(M, N)$.