Oppgave

Du har gått deg vill inn i et stort herskapshus. Dette herskapshuset har en struktur der kvadratiske rom ligger i et rutenett i øst-vestlig og nord-sørlig retning, med $M$ kolonner i øst-vestlig retning og $N$ rader i nord-sørlig retning, totalt $M \times N$ rom. Rommet i den $x$-te kolonnen fra vest ($1 \le x \le M$) og den $y$-te raden fra sør ($1 \le y \le N$) betegnes med $(x, y)$.

Hvert par av $2$ rom som ligger ved siden av hverandre i østlig, vestlig, sørlig eller nordlig retning, er forbundet med en dør midt på veggen. Hver dør er enten lukket (umulig å passere) eller åpen (mulig å passere). Når en dør er åpen, tar det $1$ minutt å bevege seg mellom midten av disse rommene. I tillegg er det en bryter i midten av noen rom; hvis du holder en bryter inne i $1$ minutt, byttes åpen/lukket-tilstanden for alle dørene i herskapshuset om.

Nå er alle dører som forbinder $2$ naborom i øst-vestlig retning lukket, og alle dører som forbinder $2$ naborom i nord-sørlig retning åpne. Du befinner deg nå i midten av rom $(1, 1)$, og du ønsker å bevege deg til midten av rom $(M, N)$ på kortest mulig tid.

Oppgavebeskrivelse

Gitt størrelsen $M, N$ på herskapshuset samt posisjonene $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ til de $K$ rommene som har en bryter, skriv et program som finner det minste antallet minutter som kreves for å bevege seg fra midten av rom $(1, 1)$ til midten av rom $(M, N)$, med start fra tilstanden der alle dører som forbinder $2$ naborom i øst-vestlig retning er lukket og alle dører som forbinder $2$ naborom i nord-sørlig retning er åpne. Hvis det derimot ikke er mulig å nå rom $(M, N)$, skal programmet angi dette.

Begrensninger

• $2 \le M \le 100000$: antallet rom i øst-vestlig retning i herskapshuset.
• $2 \le N \le 100000$: antallet rom i nord-sørlig retning i herskapshuset.
• $1 \le K \le 200000$: antallet rom med bryter.
• $1 \le X_i \le M$: posisjonen i øst-vestlig retning for et rom med bryter.
• $1 \le Y_i \le N$: posisjonen i nord-sørlig retning for et rom med bryter.

Inndata

Les følgende data fra standard inndata.

• På linje $1$ står heltallene $M, N, K$ adskilt med mellomrom. $M$ angir antallet rom i øst-vestlig retning i herskapshuset, $N$ angir antallet rom i nord-sørlig retning i herskapshuset, og $K$ angir antallet rom med bryter.
• På den $i$-te linjen ($1 \le i \le K$) av de neste $K$ linjene står heltallene $X_i, Y_i$ adskilt med mellomrom. Dette betyr at det er en bryter i midten av rom $(X_i, Y_i)$. De $K$ parene $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ er parvis forskjellige.

Utdata

Skriv ut et heltall på $1$ linje til standard utdata som angir det minste antallet minutter som trengs for forflytningen. Hvis det ikke er mulig å nå rom $(M, N)$, skal du i stedet skrive ut heltallet $-1$.

Vurderingskriterier

• For $20\%$ av poengene gjelder $M \le 1000$ og $N \le 1000$.
• For $30\%$ av poengene gjelder $K \le 2000$.
• For $50\%$ av poengene gjelder minst ett av disse $2$ kravene. Dessuten finnes det ingen testdata som oppfyller begge disse $2$ kravene samtidig.

Eksempel 1

Inndata

3 2 1
1 2

Utdata

4

Forklaring

I dette eksempelet kan du bevege deg fra midten av rom $(1, 1)$ til midten av rom $(3, 2)$ på $4$ minutter ved hjelp av følgende handlinger, og dette er kortest mulig tid:

• Gå til midten av rom $(1, 2)$.
• Trykk på bryteren i midten av rom $(1, 2)$.
• Gå til midten av rom $(2, 2)$.
• Gå til midten av rom $(3, 2)$.

Tilstanden til herskapshuset underveis er vist i figuren nedenfor. I figuren er høyre retning øst, oppover er nord, symbolet $\times$ viser posisjonen din, og symbolet $\bigcirc$ viser en bryter.

Eksempel 2

Inndata

3 2 1
2 1

Utdata

-1

Forklaring

I dette eksempelet kan du ikke nå rom $(3, 2)$.

Eksempel 3

Inndata

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

Forklaring

I dette eksempelet er starttilstanden til herskapshuset slik som vist i figuren nedenfor. Merk at det også kan være en bryter i midten av rom $(1, 1)$ eller rom $(M, N)$.