Treść zadania

Zabłądziłeś w wielkiej rezydencji. Rezydencja ta ma strukturę siatki kwadratowych pokoi ułożonych w kierunkach wschód-zachód oraz północ-południe, liczącej $M$ kolumn w kierunku wschód-zachód oraz $N$ wierszy w kierunku północ-południe, co daje łącznie $M \times N$ pokoi. Pokój znajdujący się w $x$-tej kolumnie od zachodu ($1 \le x \le M$) oraz $y$-tym wierszu od południa ($1 \le y \le N$) oznaczamy przez $(x, y)$.

Każde $2$ pokoje sąsiadujące ze sobą w kierunku wschodnim, zachodnim, południowym lub północnym są połączone drzwiami znajdującymi się na środku ściany. Każde drzwi są albo zamknięte (nieprzejezdne), albo otwarte (przejezdne). Gdy drzwi są otwarte, przemieszczenie się pomiędzy środkami tych pokoi zajmuje $1$ minutę. Ponadto na środku niektórych pokoi znajduje się przełącznik; przytrzymywanie wciśniętego przełącznika przez $1$ minutę powoduje zmianę stanu otwarcia/zamknięcia wszystkich drzwi w rezydencji na przeciwny.

Obecnie wszystkie drzwi łączące $2$ pokoje sąsiadujące w kierunku wschód-zachód są zamknięte, a wszystkie drzwi łączące $2$ pokoje sąsiadujące w kierunku północ-południe są otwarte. Znajdujesz się teraz na środku pokoju $(1, 1)$ i chcesz w jak najkrótszym czasie przemieścić się na środek pokoju $(M, N)$.

Zadanie

Mając dane wymiary rezydencji $M, N$ oraz położenia $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ tych $K$ pokoi, w których znajdują się przełączniki, napisz program, który wyznaczy minimalną liczbę minut potrzebnych na przemieszczenie się ze środka pokoju $(1, 1)$ na środek pokoju $(M, N)$, zaczynając od stanu, w którym wszystkie drzwi łączące $2$ pokoje sąsiadujące w kierunku wschód-zachód są zamknięte, a wszystkie drzwi łączące $2$ pokoje sąsiadujące w kierunku północ-południe są otwarte. Jeśli jednak dotarcie do pokoju $(M, N)$ jest niemożliwe, należy to wskazać.

Ograniczenia

• $2 \le M \le 100000$: liczba pokoi rezydencji w kierunku wschód-zachód.
• $2 \le N \le 100000$: liczba pokoi rezydencji w kierunku północ-południe.
• $1 \le K \le 200000$: liczba pokoi z przełącznikiem.
• $1 \le X_i \le M$: położenie pokoju z przełącznikiem w kierunku wschód-zachód.
• $1 \le Y_i \le N$: położenie pokoju z przełącznikiem w kierunku północ-południe.

Wejście

Wczytaj następujące dane ze standardowego wejścia.

• W wierszu $1$ zapisane są oddzielone spacjami liczby całkowite $M, N, K$. $M$ oznacza liczbę pokoi rezydencji w kierunku wschód-zachód, $N$ oznacza liczbę pokoi rezydencji w kierunku północ-południe, natomiast $K$ oznacza liczbę pokoi z przełącznikiem.
• W $i$-tym wierszu ($1 \le i \le K$) spośród kolejnych $K$ wierszy zapisane są oddzielone spacją liczby całkowite $X_i, Y_i$. Oznacza to, że na środku pokoju $(X_i, Y_i)$ znajduje się przełącznik. $K$ par $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ jest parami różnych.

Wyjście

Wypisz na standardowe wyjście w $1$ wierszu liczbę całkowitą oznaczającą minimalną liczbę minut potrzebnych na przemieszczenie się. Jeśli jednak dotarcie do pokoju $(M, N)$ jest niemożliwe, wypisz zamiast tego liczbę całkowitą $-1$.

Kryteria oceniania

• Dla $20\%$ łącznej liczby punktów spełnione są warunki $M \le 1000$ oraz $N \le 1000$.
• Dla $30\%$ łącznej liczby punktów spełniony jest warunek $K \le 2000$.
• Dla $50\%$ łącznej liczby punktów spełniony jest co najmniej jeden z tych $2$ warunków. Ponadto nie ma danych testowych spełniających oba te $2$ warunki jednocześnie.

Przykład 1

Wejście

3 2 1
1 2

Wyjście

4

Wyjaśnienie

W tym przykładzie można przemieścić się ze środka pokoju $(1, 1)$ na środek pokoju $(3, 2)$ w $4$ minuty, wykonując następujące czynności, i jest to czas najkrótszy:

• Przemieść się na środek pokoju $(1, 2)$.
• Naciśnij przełącznik na środku pokoju $(1, 2)$.
• Przemieść się na środek pokoju $(2, 2)$.
• Przemieść się na środek pokoju $(3, 2)$.

Stan rezydencji w tym czasie przedstawiono na poniższym rysunku. Na rysunku kierunek w prawo to wschód, kierunek w górę to północ, znak $\times$ oznacza Twoją pozycję, a znak $\bigcirc$ oznacza przełącznik.

Przykład 2

Wejście

3 2 1
2 1

Wyjście

-1

Wyjaśnienie

W tym przykładzie nie możesz dotrzeć do pokoju $(3, 2)$.

Przykład 3

Wejście

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

Wyjście

25

Wyjaśnienie

W tym przykładzie początkowy stan rezydencji wygląda tak, jak na poniższym rysunku. Zauważ, że przełącznik może znajdować się również na środku pokoju $(1, 1)$ lub pokoju $(M, N)$.