Tehtävä

Olet eksynyt suureen kartanoon. Tässä kartanossa neliönmuotoiset huoneet muodostavat ruudukon itä–länsi- ja pohjois–etelä-suunnissa siten, että itä–länsi-suunnassa on $M$ saraketta ja pohjois–etelä-suunnassa $N$ riviä, eli yhteensä $M \times N$ huonetta. Lännestä lukien $x$:nnessä sarakkeessa ($1 \le x \le M$) ja etelästä lukien $y$:nnessä rivissä ($1 \le y \le N$) olevaa huonetta merkitään $(x, y)$.

Jokaisen itä-, länsi-, etelä- tai pohjoissuunnassa vierekkäisen $2$ huoneen välillä on seinän keskellä oleva ovi. Jokainen ovi on joko suljetussa (kulkukelvottomassa) tilassa tai avoimessa (kulkukelpoisessa) tilassa. Kun ovi on auki, siirtyminen näiden huoneiden keskipisteiden välillä vie $1$ minuutin. Lisäksi joidenkin huoneiden keskellä on katkaisija; jos katkaisijaa pitää painettuna $1$ minuutin ajan, kartanon kaikkien ovien auki/kiinni-tila vaihtuu päinvastaiseksi.

Tällä hetkellä kaikki itä–länsi-suunnassa vierekkäiset $2$ huonetta yhdistävät ovet ovat kiinni, ja kaikki pohjois–etelä-suunnassa vierekkäiset $2$ huonetta yhdistävät ovet ovat auki. Olet nyt huoneen $(1, 1)$ keskellä ja haluat siirtyä huoneen $(M, N)$ keskelle mahdollisimman lyhyessä ajassa.

Tehtävänanto

Kun annetaan kartanon koko $M, N$ sekä niiden $K$ huoneen sijainnit $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$, joissa on katkaisija, kirjoita ohjelma, joka selvittää, kuinka monta minuuttia vähintään kuluu siirtymiseen huoneen $(1, 1)$ keskeltä huoneen $(M, N)$ keskelle, kun lähdetään tilanteesta, jossa kaikki itä–länsi-suunnassa vierekkäiset $2$ huonetta yhdistävät ovet ovat kiinni ja kaikki pohjois–etelä-suunnassa vierekkäiset $2$ huonetta yhdistävät ovet ovat auki. Jos huoneeseen $(M, N)$ ei ole mahdollista päästä, ilmoita siitä.

Rajoitukset

• $2 \le M \le 100000$: kartanon huoneiden lukumäärä itä–länsi-suunnassa.
• $2 \le N \le 100000$: kartanon huoneiden lukumäärä pohjois–etelä-suunnassa.
• $1 \le K \le 200000$: katkaisijallisten huoneiden lukumäärä.
• $1 \le X_i \le M$: katkaisijallisen huoneen sijainti itä–länsi-suunnassa.
• $1 \le Y_i \le N$: katkaisijallisen huoneen sijainti pohjois–etelä-suunnassa.

Syöte

Lue seuraavat tiedot vakiosyötteestä.

• Rivillä $1$ on välilyönnein erotettuina kokonaisluvut $M, N, K$. $M$ ilmoittaa kartanon huoneiden lukumäärän itä–länsi-suunnassa, $N$ ilmoittaa kartanon huoneiden lukumäärän pohjois–etelä-suunnassa ja $K$ ilmoittaa katkaisijallisten huoneiden lukumäärän.
• Seuraavien $K$ rivin $i$:nnellä rivillä ($1 \le i \le K$) on välilyönnillä erotettuina kokonaisluvut $X_i, Y_i$. Tämä tarkoittaa, että huoneen $(X_i, Y_i)$ keskellä on katkaisija. Kaikki $K$ paria $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ ovat keskenään erisuuria.

Tuloste

Tulosta vakiotulosteeseen $1$ riville kokonaisluku, joka ilmoittaa siirtymiseen tarvittavan vähimmäisajan minuutteina. Jos huoneeseen $(M, N)$ ei kuitenkaan ole mahdollista päästä, tulosta sen sijaan kokonaisluku $-1$.

Arvosteluperusteet

• Arvosteluaineistosta $20\%$:ssa pisteistä pätee $M \le 1000$ ja $N \le 1000$.
• Arvosteluaineistosta $30\%$:ssa pisteistä pätee $K \le 2000$.
• Arvosteluaineistosta $50\%$:ssa pisteistä pätee vähintään toinen näistä $2$ ehdosta. Lisäksi mikään arvosteluaineisto ei täytä molempia näistä $2$ ehdosta samanaikaisesti.

Esimerkki 1

Syöte

3 2 1
1 2

Tuloste

4

Selitys

Tässä esimerkissä huoneen $(1, 1)$ keskeltä voidaan siirtyä huoneen $(3, 2)$ keskelle $4$ minuutissa seuraavilla toimilla, ja tämä on lyhin mahdollinen aika:

• Siirry huoneen $(1, 2)$ keskelle.
• Paina huoneen $(1, 2)$ keskellä olevaa katkaisijaa.
• Siirry huoneen $(2, 2)$ keskelle.
• Siirry huoneen $(3, 2)$ keskelle.

Kartanon tila tämän aikana on esitetty alla olevassa kuvassa. Kuvassa oikealle on itä, ylös on pohjoinen, merkki $\times$ kuvaa sijaintiasi ja merkki $\bigcirc$ kuvaa katkaisijaa.

Esimerkki 2

Syöte

3 2 1
2 1

Tuloste

-1

Selitys

Tässä esimerkissä et voi päästä huoneeseen $(3, 2)$.

Esimerkki 3

Syöte

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

Tuloste

25

Selitys

Tässä esimerkissä kartanon alkutila on alla olevan kuvan mukainen. Huomaa, että katkaisija voi olla myös huoneen $(1, 1)$ tai huoneen $(M, N)$ keskellä.