Énoncé

Vous vous êtes égaré dans un grand manoir. Ce manoir a une structure dans laquelle des pièces carrées sont disposées en grille selon les directions est-ouest et nord-sud, avec $M$ colonnes dans la direction est-ouest et $N$ lignes dans la direction nord-sud, soit un total de $M \times N$ pièces. La pièce située dans la $x$-ème colonne à partir de l'ouest ($1 \le x \le M$) et la $y$-ème ligne à partir du sud ($1 \le y \le N$) est notée $(x, y)$.

Deux ($2$) pièces adjacentes selon les directions est, ouest, sud ou nord sont reliées par une porte située au centre du mur qui les sépare. Chaque porte est soit fermée (infranchissable), soit ouverte (franchissable). Lorsqu'une porte est ouverte, il faut $1$ minute pour se déplacer entre les centres de ces pièces. De plus, au centre de certaines pièces se trouve un interrupteur ; si l'on maintient un interrupteur enfoncé pendant $1$ minute, l'état ouvert/fermé de toutes les portes du manoir s'inverse.

Actuellement, toutes les portes reliant $2$ pièces adjacentes dans la direction est-ouest sont fermées, et toutes les portes reliant $2$ pièces adjacentes dans la direction nord-sud sont ouvertes. Vous vous trouvez actuellement au centre de la pièce $(1, 1)$, et vous souhaitez vous déplacer jusqu'au centre de la pièce $(M, N)$ le plus rapidement possible.

Tâche

Étant donné la taille $M, N$ du manoir ainsi que les positions $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ des $K$ pièces munies d'un interrupteur, écrivez un programme pour déterminer le nombre minimum de minutes nécessaires pour aller du centre de la pièce $(1, 1)$ au centre de la pièce $(M, N)$, en partant de l'état où toutes les portes reliant $2$ pièces adjacentes dans la direction est-ouest sont fermées et toutes les portes reliant $2$ pièces adjacentes dans la direction nord-sud sont ouvertes. Toutefois, s'il est impossible d'atteindre la pièce $(M, N)$, indiquez-le.

Contraintes

• $2 \le M \le 100000$ : le nombre de pièces du manoir dans la direction est-ouest.
• $2 \le N \le 100000$ : le nombre de pièces du manoir dans la direction nord-sud.
• $1 \le K \le 200000$ : le nombre de pièces munies d'un interrupteur.
• $1 \le X_i \le M$ : la position dans la direction est-ouest d'une pièce munie d'un interrupteur.
• $1 \le Y_i \le N$ : la position dans la direction nord-sud d'une pièce munie d'un interrupteur.

Entrée

Lisez les données suivantes depuis l'entrée standard.

• Sur la ligne $1$ sont écrits les entiers $M, N, K$ séparés par des espaces. $M$ représente le nombre de pièces du manoir dans la direction est-ouest, $N$ représente le nombre de pièces du manoir dans la direction nord-sud, et $K$ représente le nombre de pièces munies d'un interrupteur.
• Sur la $i$-ème ligne ($1 \le i \le K$) des $K$ lignes suivantes sont écrits les entiers $X_i, Y_i$ séparés par un espace. Cela indique qu'il y a un interrupteur au centre de la pièce $(X_i, Y_i)$. Les $K$ couples $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ sont deux à deux distincts.

Sortie

Affichez sur $1$ ligne sur la sortie standard l'entier représentant le nombre minimum de minutes nécessaires pour le déplacement. Toutefois, s'il est impossible d'atteindre la pièce $(M, N)$, affichez l'entier $-1$ à la place.

Critères d'évaluation

• Pour $20\%$ des points, on a $M \le 1000$ et $N \le 1000$.
• Pour $30\%$ des points, on a $K \le 2000$.
• Pour $50\%$ des points, au moins l'une de ces $2$ conditions est satisfaite. De plus, aucune donnée d'évaluation ne satisfait simultanément ces $2$ conditions.

Exemple 1

Entrée

3 2 1
1 2

Sortie

4

Explication

Dans cet exemple, vous pouvez vous déplacer du centre de la pièce $(1, 1)$ au centre de la pièce $(3, 2)$ en $4$ minutes grâce aux actions suivantes, ce qui est optimal :

• Se déplacer vers le centre de la pièce $(1, 2)$.
• Appuyer sur l'interrupteur au centre de la pièce $(1, 2)$.
• Se déplacer vers le centre de la pièce $(2, 2)$.
• Se déplacer vers le centre de la pièce $(3, 2)$.

L'état du manoir au cours de ces actions est illustré ci-dessous. Sur la figure, la droite correspond à l'est, le haut correspond au nord, le symbole $\times$ représente votre position et le symbole $\bigcirc$ représente un interrupteur.

Exemple 2

Entrée

3 2 1
2 1

Sortie

-1

Explication

Dans cet exemple, vous ne pouvez pas atteindre la pièce $(3, 2)$.

Exemple 3

Entrée

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

Sortie

25

Explication

Dans cet exemple, l'état initial du manoir est illustré ci-dessous. Notez qu'il peut également y avoir un interrupteur au centre de la pièce $(1, 1)$ ou de la pièce $(M, N)$.