Problema

Ti sei smarrito in una grande villa. Questa villa ha una struttura in cui stanze quadrate sono disposte a griglia nelle direzioni est-ovest e nord-sud, con $M$ colonne in direzione est-ovest e $N$ righe in direzione nord-sud, per un totale di $M \times N$ stanze. La stanza nella $x$-esima colonna da ovest ($1 \le x \le M$) e nella $y$-esima riga da sud ($1 \le y \le N$) è indicata con $(x, y)$.

Ogni coppia di $2$ stanze adiacenti in direzione est, ovest, sud o nord è collegata da una porta situata al centro della parete. Ciascuna porta si trova nello stato chiuso (impraticabile) oppure nello stato aperto (praticabile). Quando una porta è aperta, occorre $1$ minuto per spostarsi tra il centro di quelle stanze. Inoltre, al centro di alcune stanze c'è un interruttore; se si tiene premuto un interruttore per $1$ minuto, lo stato di apertura/chiusura di tutte le porte della villa si inverte.

In questo momento, tutte le porte che collegano $2$ stanze adiacenti in direzione est-ovest sono chiuse, e tutte le porte che collegano $2$ stanze adiacenti in direzione nord-sud sono aperte. Ti trovi attualmente al centro della stanza $(1, 1)$ e vuoi spostarti al centro della stanza $(M, N)$ nel minor tempo possibile.

Compito

Date le dimensioni $M, N$ della villa e le posizioni $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ delle $K$ stanze dotate di interruttore, scrivi un programma per trovare il numero minimo di minuti necessari per spostarsi dal centro della stanza $(1, 1)$ al centro della stanza $(M, N)$, partendo dallo stato in cui tutte le porte che collegano $2$ stanze adiacenti in direzione est-ovest sono chiuse e tutte le porte che collegano $2$ stanze adiacenti in direzione nord-sud sono aperte. Tuttavia, se non è possibile raggiungere la stanza $(M, N)$, indicalo.

Vincoli

• $2 \le M \le 100000$: il numero di stanze della villa in direzione est-ovest.
• $2 \le N \le 100000$: il numero di stanze della villa in direzione nord-sud.
• $1 \le K \le 200000$: il numero di stanze dotate di interruttore.
• $1 \le X_i \le M$: la posizione in direzione est-ovest di una stanza dotate di interruttore.
• $1 \le Y_i \le N$: la posizione in direzione nord-sud di una stanza dotata di interruttore.

Input

Leggi i seguenti dati dallo standard input.

• Sulla riga $1$ sono scritti gli interi $M, N, K$ separati da spazi. $M$ rappresenta il numero di stanze della villa in direzione est-ovest, $N$ rappresenta il numero di stanze della villa in direzione nord-sud e $K$ rappresenta il numero di stanze dotate di interruttore.
• Sulla $i$-esima riga ($1 \le i \le K$) delle successive $K$ righe sono scritti gli interi $X_i, Y_i$ separati da uno spazio. Ciò indica che c'è un interruttore al centro della stanza $(X_i, Y_i)$. Le $K$ coppie $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ sono tutte distinte tra loro.

Output

Stampa su $1$ riga sullo standard output l'intero che rappresenta il numero minimo di minuti necessari per lo spostamento. Tuttavia, se non è possibile raggiungere la stanza $(M, N)$, stampa invece l'intero $-1$.

Criteri di valutazione

• Per il $20\%$ del punteggio totale, valgono $M \le 1000$ e $N \le 1000$.
• Per il $30\%$ del punteggio totale, vale $K \le 2000$.
• Per il $50\%$ del punteggio totale, vale almeno una di queste $2$ condizioni. Inoltre, non esistono dati di valutazione che soddisfino entrambe queste $2$ condizioni.

Esempio 1

Input

3 2 1
1 2

Output

4

Spiegazione

In questo esempio è possibile spostarsi dal centro della stanza $(1, 1)$ al centro della stanza $(3, 2)$ in $4$ minuti mediante le seguenti azioni, e questo è il tempo minimo:

• Spostarsi al centro della stanza $(1, 2)$.
• Premere l'interruttore al centro della stanza $(1, 2)$.
• Spostarsi al centro della stanza $(2, 2)$.
• Spostarsi al centro della stanza $(3, 2)$.

Lo stato della villa in questo processo è rappresentato nella figura sottostante. Nella figura la direzione destra è l'est, la direzione alta è il nord, il simbolo $\times$ indica la tua posizione e il simbolo $\bigcirc$ indica un interruttore.

Esempio 2

Input

3 2 1
2 1

Output

-1

Spiegazione

In questo esempio non puoi raggiungere la stanza $(3, 2)$.

Esempio 3

Input

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

Output

25

Spiegazione

In questo esempio lo stato iniziale della villa è quello mostrato nella figura sottostante. Nota che potrebbe esserci un interruttore anche al centro della stanza $(1, 1)$ o della stanza $(M, N)$.