題目描述

你迷路闖入咗一間好大嘅大宅。呢間大宅嘅結構係正方形嘅房間喺東西南北方向排成格仔網狀，東西方向有 $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)$ 嘅正中間亦有可能有掣。