題目描述

你迷路闖入了一座巨大的宅邸。這座宅邸的結構是正方形的房間在東西南北方向上呈網格狀排列，東西方向有 $M$ 列，南北方向有 $N$ 行，共有 $M \times N$ 個房間。由西往東數第 $x$ 列（$1 \le x \le M$）、由南往北數第 $y$ 行（$1 \le y \le N$）的房間表示為 $(x, y)$。

在東西南北方向上相鄰的任意 $2$ 個房間之間，都由牆壁中央的一扇門相連。每扇門都處於關閉而無法通行的狀態，或打開而可以通行的狀態之一。當門打開時，在這些房間的中央之間移動需要花費 $1$ 分鐘。此外，部分房間的中央設有一個開關，持續按住開關 $1$ 分鐘，宅邸內所有門的開關狀態都會反轉。

現在，連接東西方向相鄰的 $2$ 個房間的所有門都是關閉的，連接南北方向相鄰的 $2$ 個房間的所有門都是打開的。你現在位於房間 $(1, 1)$ 的中央，希望用最短的時間移動到房間 $(M, N)$ 的中央。

任務

給定宅邸的大小 $M, N$ 以及設有開關的 $K$ 個房間的位置 $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$，請撰寫一個程式，求出從連接東西方向相鄰的 $2$ 個房間的所有門關閉、連接南北方向相鄰的 $2$ 個房間的所有門打開的狀態開始，從房間 $(1, 1)$ 的中央移動到房間 $(M, N)$ 的中央最少需要多少分鐘。但是，如果無法到達房間 $(M, N)$，請指出這一點。

限制

• $2 \le M \le 100000$：宅邸在東西方向上的房間個數。
• $2 \le N \le 100000$：宅邸在南北方向上的房間個數。
• $1 \le K \le 200000$：設有開關的房間個數。
• $1 \le X_i \le M$：設有開關的房間在東西方向上的位置。
• $1 \le Y_i \le N$：設有開關的房間在南北方向上的位置。

輸入格式

從標準輸入讀入以下資料。

• 第 $1$ 行包含以空格分隔的整數 $M, N, K$。$M$ 表示宅邸在東西方向上的房間個數，$N$ 表示宅邸在南北方向上的房間個數，$K$ 表示設有開關的房間個數。
• 接下來的 $K$ 行中的第 $i$ 行（$1 \le i \le K$）包含以空格分隔的整數 $X_i, Y_i$。這表示在房間 $(X_i, Y_i)$ 的中央設有一個開關。$K$ 個二元組 $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ 互不相同。

輸出格式

向標準輸出印出 $1$ 行，包含一個整數，表示移動所需的最少分鐘數。但是，如果無法到達房間 $(M, N)$，則改為輸出整數 $-1$。

評分標準

• 在佔總分 $20\%$ 的評分資料中，滿足 $M \le 1000$ 且 $N \le 1000$。
• 在佔總分 $30\%$ 的評分資料中，滿足 $K \le 2000$。
• 在佔總分 $50\%$ 的評分資料中，至少滿足上述 $2$ 個條件之一。此外，不存在同時滿足上述 $2$ 個條件的評分資料。

範例 1

輸入

3 2 1
1 2

輸出

4

範例說明

在這個範例中，透過以下行動可以在 $4$ 分鐘內從房間 $(1, 1)$ 的中央移動到房間 $(3, 2)$ 的中央，且這是最短時間：

• 移動到房間 $(1, 2)$ 的中央。
• 按下房間 $(1, 2)$ 中央的開關。
• 移動到房間 $(2, 2)$ 的中央。
• 移動到房間 $(3, 2)$ 的中央。

此過程中宅邸的狀態如下圖所示。在圖中，右方為東，上方為北，$\times$ 記號表示你的位置，$\bigcirc$ 記號表示開關。

範例 2

輸入

3 2 1
2 1

輸出

-1

範例說明

在這個範例中，你無法到達房間 $(3, 2)$。

範例 3

輸入

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

輸出

25

範例說明

在這個範例中，宅邸的初始狀態如下圖所示。注意房間 $(1, 1)$ 或房間 $(M, N)$ 的中央也有可能設有開關。