Problembeschreibung

Du hast dich in ein großes Herrenhaus verirrt. Dieses Herrenhaus hat eine Struktur, bei der quadratische Räume gitterförmig in Ost-West- und Nord-Süd-Richtung angeordnet sind, mit $M$ Spalten in Ost-West-Richtung und $N$ Zeilen in Nord-Süd-Richtung, also insgesamt $M \times N$ Räumen. Der Raum in der $x$-ten Spalte von Westen ($1 \le x \le M$) und der $y$-ten Zeile von Süden ($1 \le y \le N$) wird mit $(x, y)$ bezeichnet.

Je $2$ in Ost-, West-, Süd- oder Nordrichtung benachbarte Räume sind durch eine Tür in der Mitte der Wand miteinander verbunden. Jede Tür befindet sich entweder in einem geschlossenen (unpassierbaren) Zustand oder in einem offenen (passierbaren) Zustand. Wenn eine Tür geöffnet ist, dauert es $1$ Minute, um sich zwischen den Mitten dieser Räume zu bewegen. Außerdem befindet sich in der Mitte einiger Räume ein Schalter; wenn man einen Schalter $1$ Minute lang gedrückt hält, kehrt sich der Öffnungs-/Schließzustand aller Türen im Herrenhaus um.

Derzeit sind alle Türen, die $2$ in Ost-West-Richtung benachbarte Räume verbinden, geschlossen, und alle Türen, die $2$ in Nord-Süd-Richtung benachbarte Räume verbinden, sind geöffnet. Du befindest dich derzeit in der Mitte von Raum $(1, 1)$ und möchtest dich in kürzester Zeit zur Mitte von Raum $(M, N)$ bewegen.

Aufgabe

Gegeben die Größe $M, N$ des Herrenhauses sowie die Positionen $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ der $K$ Räume mit einem Schalter, schreibe ein Programm, das berechnet, wie viele Minuten mindestens benötigt werden, um sich von der Mitte von Raum $(1, 1)$ zur Mitte von Raum $(M, N)$ zu bewegen, ausgehend von dem Zustand, in dem alle Türen zwischen $2$ in Ost-West-Richtung benachbarten Räumen geschlossen und alle Türen zwischen $2$ in Nord-Süd-Richtung benachbarten Räumen geöffnet sind. Falls es jedoch unmöglich ist, Raum $(M, N)$ zu erreichen, gib dies an.

Einschränkungen

• $2 \le M \le 100000$: die Anzahl der Räume des Herrenhauses in Ost-West-Richtung.
• $2 \le N \le 100000$: die Anzahl der Räume des Herrenhauses in Nord-Süd-Richtung.
• $1 \le K \le 200000$: die Anzahl der Räume mit einem Schalter.
• $1 \le X_i \le M$: die Position eines Raums mit Schalter in Ost-West-Richtung.
• $1 \le Y_i \le N$: die Position eines Raums mit Schalter in Nord-Süd-Richtung.

Eingabe

Lies die folgenden Daten von der Standardeingabe.

• In Zeile $1$ stehen die durch Leerzeichen getrennten ganzen Zahlen $M, N, K$. $M$ gibt die Anzahl der Räume des Herrenhauses in Ost-West-Richtung an, $N$ gibt die Anzahl der Räume des Herrenhauses in Nord-Süd-Richtung an, und $K$ gibt die Anzahl der Räume mit einem Schalter an.
• In der $i$-ten Zeile ($1 \le i \le K$) der folgenden $K$ Zeilen stehen die durch ein Leerzeichen getrennten ganzen Zahlen $X_i, Y_i$. Dies bedeutet, dass sich in der Mitte von Raum $(X_i, Y_i)$ ein Schalter befindet. Die $K$ Paare $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ sind paarweise verschieden.

Ausgabe

Gib auf der Standardausgabe in $1$ Zeile die ganze Zahl aus, welche die minimale Anzahl an Minuten für die Bewegung angibt. Falls es jedoch unmöglich ist, Raum $(M, N)$ zu erreichen, gib stattdessen die ganze Zahl $-1$ aus.

Bewertungskriterien

• Für $20\%$ der Gesamtpunktzahl gilt $M \le 1000$ und $N \le 1000$.
• Für $30\%$ der Gesamtpunktzahl gilt $K \le 2000$.
• Für $50\%$ der Gesamtpunktzahl ist mindestens eine dieser $2$ Bedingungen erfüllt. Außerdem gibt es keine Bewertungsdaten, die beide dieser $2$ Bedingungen gleichzeitig erfüllen.

Beispiel 1

Eingabe

3 2 1
1 2

Ausgabe

4

Erklärung

In diesem Beispiel kannst du dich durch die folgenden Aktionen in $4$ Minuten von der Mitte von Raum $(1, 1)$ zur Mitte von Raum $(3, 2)$ bewegen, was die kürzeste Zeit ist:

• Bewege dich zur Mitte von Raum $(1, 2)$.
• Drücke den Schalter in der Mitte von Raum $(1, 2)$.
• Bewege dich zur Mitte von Raum $(2, 2)$.
• Bewege dich zur Mitte von Raum $(3, 2)$.

Der Zustand des Herrenhauses währenddessen ist in der folgenden Abbildung dargestellt. In der Abbildung ist rechts Osten, oben Norden, das Symbol $\times$ steht für deine Position und das Symbol $\bigcirc$ steht für einen Schalter.

Beispiel 2

Eingabe

3 2 1
2 1

Ausgabe

-1

Erklärung

In diesem Beispiel kannst du Raum $(3, 2)$ nicht erreichen.

Beispiel 3

Eingabe

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

Ausgabe

25

Erklärung

In diesem Beispiel sieht der Anfangszustand des Herrenhauses wie in der folgenden Abbildung aus. Beachte, dass sich auch in der Mitte von Raum $(1, 1)$ oder Raum $(M, N)$ ein Schalter befinden kann.