Verkefni

Þú hefur villst inn í stórt setur. Þetta setur er þannig uppbyggt að ferningslaga herbergi liggja í grind í austur-vestur og norður-suður, með $M$ dálkum í austur-vestur og $N$ röðum í norður-suður, samtals $M \times N$ herbergi. Herbergið í $x$-ta dálki frá vestri ($1 \le x \le M$) og $y$-tu röð frá suðri ($1 \le y \le N$) er táknað með $(x, y)$.

Milli hverra $2$ herbergja sem liggja saman í austur, vestur, suður eða norður eru dyr á miðjum veggnum. Hverjar dyr eru annaðhvort lokaðar (ófærar) eða opnar (færar). Þegar dyr eru opnar tekur $1$ mínútu að fara á milli miðja þessara herbergja. Einnig er rofi í miðju sumra herbergja; ef ýtt er samfellt á rofa í $1$ mínútu snýst opið/lokað ástand allra dyra í setrinu við.

Núna eru allar dyr sem tengja $2$ aðliggjandi herbergi í austur-vestur lokaðar, og allar dyr sem tengja $2$ aðliggjandi herbergi í norður-suður opnar. Þú ert núna í miðju herbergis $(1, 1)$ og vilt komast í miðju herbergis $(M, N)$ á sem skemmstum tíma.

Viðfangsefni

Gefið er stærð setursins $M, N$ ásamt staðsetningum $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ þeirra $K$ herbergja sem hafa rofa. Skrifið forrit sem finnur lágmarksfjölda mínútna sem þarf til að fara úr miðju herbergis $(1, 1)$ í miðju herbergis $(M, N)$, ef byrjað er í því ástandi að allar dyr sem tengja $2$ aðliggjandi herbergi í austur-vestur eru lokaðar og allar dyr sem tengja $2$ aðliggjandi herbergi í norður-suður eru opnar. Ef hins vegar er ómögulegt að komast í herbergi $(M, N)$ skal gefa það til kynna.

Takmarkanir

• $2 \le M \le 100000$: fjöldi herbergja setursins í austur-vestur.
• $2 \le N \le 100000$: fjöldi herbergja setursins í norður-suður.
• $1 \le K \le 200000$: fjöldi herbergja með rofa.
• $1 \le X_i \le M$: staðsetning herbergis með rofa í austur-vestur.
• $1 \le Y_i \le N$: staðsetning herbergis með rofa í norður-suður.

Inntak

Lesið eftirfarandi gögn af staðalinntaki.

• Á línu $1$ eru heiltölurnar $M, N, K$ skrifaðar aðskildar með bilum. $M$ táknar fjölda herbergja setursins í austur-vestur, $N$ táknar fjölda herbergja setursins í norður-suður og $K$ táknar fjölda herbergja með rofa.
• Á $i$-tu línu ($1 \le i \le K$) af næstu $K$ línum eru heiltölurnar $X_i, Y_i$ skrifaðar aðskildar með bili. Þetta gefur til kynna að rofi sé í miðju herbergis $(X_i, Y_i)$. Tvenndirnar $K$, $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$, eru innbyrðis ólíkar.

Úttak

Skrifið út í $1$ línu á staðalúttak heiltölu sem táknar lágmarksfjölda mínútna sem ferðin tekur. Ef hins vegar er ómögulegt að komast í herbergi $(M, N)$ skal skrifa út heiltöluna $-1$ í staðinn.

Stigagjöf

• Fyrir $20\%$ heildarstiga gildir $M \le 1000$ og $N \le 1000$.
• Fyrir $30\%$ heildarstiga gildir $K \le 2000$.
• Fyrir $50\%$ heildarstiga gildir að minnsta kosti annað þessara $2$ skilyrða. Auk þess eru engin prófunargögn sem uppfylla bæði þessi $2$ skilyrði samtímis.

Dæmi 1

Inntak

3 2 1
1 2

Úttak

4

Skýring

Í þessu dæmi er hægt að fara úr miðju herbergis $(1, 1)$ í miðju herbergis $(3, 2)$ á $4$ mínútum með eftirfarandi aðgerðum, og það er stysti tíminn:

• Fara í miðju herbergis $(1, 2)$.
• Ýta á rofann í miðju herbergis $(1, 2)$.
• Fara í miðju herbergis $(2, 2)$.
• Fara í miðju herbergis $(3, 2)$.

Ástand setursins á meðan þessu stendur er sýnt á myndinni hér að neðan. Á myndinni er hægri austur, upp er norður, merkið $\times$ táknar staðsetningu þína og merkið $\bigcirc$ táknar rofa.

Dæmi 2

Inntak

3 2 1
2 1

Úttak

-1

Skýring

Í þessu dæmi getur þú ekki komist í herbergi $(3, 2)$.

Dæmi 3

Inntak

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

Úttak

25

Skýring

Í þessu dæmi er upphafsástand setursins eins og sýnt er á myndinni hér að neðan. Athugið að það getur líka verið rofi í miðju herbergis $(1, 1)$ eða herbergis $(M, N)$.