Problem

Du har gått vilse in i en stor herrgård. Denna herrgård har en struktur där kvadratiska rum är ordnade i ett rutnät i öst-västlig och nord-sydlig riktning, med $M$ kolumner i öst-västlig riktning och $N$ rader i nord-sydlig riktning, totalt $M \times N$ rum. Rummet i den $x$-te kolumnen från väster ($1 \le x \le M$) och den $y$-te raden från söder ($1 \le y \le N$) betecknas med $(x, y)$.

Varje par av $2$ rum som gränsar till varandra i östlig, västlig, sydlig eller nordlig riktning är förbundna med en dörr placerad i mitten av väggen. Varje dörr är antingen i ett stängt (opasserbart) tillstånd eller i ett öppet (passerbart) tillstånd. När en dörr är öppen tar det $1$ minut att förflytta sig mellan mitten av dessa rum. Dessutom finns det en strömbrytare i mitten av vissa rum; om man håller en strömbrytare intryckt under $1$ minut växlar öppet/stängt-tillståndet för alla dörrar i herrgården.

För närvarande är alla dörrar som förbinder $2$ angränsande rum i öst-västlig riktning stängda, och alla dörrar som förbinder $2$ angränsande rum i nord-sydlig riktning öppna. Du befinner dig nu i mitten av rum $(1, 1)$ och vill förflytta dig till mitten av rum $(M, N)$ på kortast möjliga tid.

Uppgift

Givet herrgårdens storlek $M, N$ samt positionerna $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ för de $K$ rummen som har en strömbrytare, skriv ett program som beräknar det minsta antalet minuter som krävs för att förflytta sig från mitten av rum $(1, 1)$ till mitten av rum $(M, N)$, med start i tillståndet där alla dörrar som förbinder $2$ angränsande rum i öst-västlig riktning är stängda och alla dörrar som förbinder $2$ angränsande rum i nord-sydlig riktning är öppna. Om det däremot är omöjligt att nå rum $(M, N)$, ange detta.

Begränsningar

• $2 \le M \le 100000$: antalet rum i öst-västlig riktning i herrgården.
• $2 \le N \le 100000$: antalet rum i nord-sydlig riktning i herrgården.
• $1 \le K \le 200000$: antalet rum med strömbrytare.
• $1 \le X_i \le M$: positionen i öst-västlig riktning för ett rum med strömbrytare.
• $1 \le Y_i \le N$: positionen i nord-sydlig riktning för ett rum med strömbrytare.

Indata

Läs följande data från standardindata.

• På rad $1$ står heltalen $M, N, K$ åtskilda av blanksteg. $M$ anger antalet rum i öst-västlig riktning i herrgården, $N$ anger antalet rum i nord-sydlig riktning i herrgården och $K$ anger antalet rum med strömbrytare.
• På den $i$-te raden ($1 \le i \le K$) av de följande $K$ raderna står heltalen $X_i, Y_i$ åtskilda av ett blanksteg. Detta anger att det finns en strömbrytare i mitten av rum $(X_i, Y_i)$. De $K$ paren $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ är parvis olika.

Utdata

Skriv ut ett heltal på $1$ rad till standardutdata som anger det minsta antalet minuter som krävs för förflyttningen. Om det är omöjligt att nå rum $(M, N)$, skriv istället ut heltalet $-1$.

Bedömningskriterier

• För $20\%$ av poängen gäller $M \le 1000$ och $N \le 1000$.
• För $30\%$ av poängen gäller $K \le 2000$.
• För $50\%$ av poängen gäller minst ett av dessa $2$ villkor. Dessutom finns det inga testdata som uppfyller båda dessa $2$ villkor samtidigt.

Exempel 1

Indata

3 2 1
1 2

Utdata

4

Förklaring

I detta exempel kan du förflytta dig från mitten av rum $(1, 1)$ till mitten av rum $(3, 2)$ på $4$ minuter genom följande handlingar, vilket är den kortaste tiden:

• Förflytta dig till mitten av rum $(1, 2)$.
• Tryck på strömbrytaren i mitten av rum $(1, 2)$.
• Förflytta dig till mitten av rum $(2, 2)$.
• Förflytta dig till mitten av rum $(3, 2)$.

Herrgårdens tillstånd under detta förlopp visas i figuren nedan. I figuren är höger öster, uppåt norr, markeringen $\times$ anger din position och markeringen $\bigcirc$ anger en strömbrytare.

Exempel 2

Indata

3 2 1
2 1

Utdata

-1

Förklaring

I detta exempel kan du inte nå rum $(3, 2)$.

Exempel 3

Indata

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

Utdata

25

Förklaring

I detta exempel ser herrgårdens ursprungliga tillstånd ut som i figuren nedan. Observera att det även kan finnas en strömbrytare i mitten av rum $(1, 1)$ eller rum $(M, N)$.