Biệt thự

Mr. X mới mua một chiếc biệt thự lớn và hiện đại. Biệt thự có thể được biểu diễn bởi một
hình chữ nhật được chia làm \(M\) cột và \(N\) hàng. Các cột được đánh số từ \(1\) tới \(M\) theo chiều
từ trái qua phải (chiều hướng Tây đến Đông). Các hàng được đánh số từ \(1\) tới \(N\) theo chiều
từ dưới lên trên (chiều hướng Nam đến Bắc). Biệt thự có \(M \times N\) phòng, phòng nằm trên cột \(i\) hàng \(j\) được ký hiệu là \((i, j)\). Hai phòng có chung cạnh sẽ có một cửa nối giữa chúng. Ban
đầu, tất cả các cửa nối \(2\) phòng theo hướng Nam-Bắc được mở, các cửa còn lại bị đóng. Đi
qua một cánh cửa mở mất \(1\) phút. Một số căn phòng được đặt công tắc kiểm soát trạng thái
của các cửa. Khi ấn, đè công tắc trong vòng \(1\) phút, mọi cánh cửa đang đóng sẽ mở, và mọi
cánh cửa đang mở sẽ đóng.

Yêu cầu: Xác định thời gian ngắn nhất đi từ phòng \((1, 1)\) tới phòng \((M, N)\).

Input

Dòng đầu tiên chứa 3 số nguyên \(M, N, K\) \((2 \leq M, N \leq 100000, 1 \leq K \leq 200000)\).

\(K\) dòng sau, mỗi dòng gồm \(2\) số nguyên \(x, y\) \((1 \leq x \leq M, 1 \leq y \leq N)\) mô tả phòng \((x, y)\) có đặt công tắc. \(K\) tọa độ phòng là phân biệt.

Output

In ra số phút ít nhất để đi từ phòng \((1, 1)\) tới phòng \((M, N)\). Nếu không đi được, in ra \(-1\).

Example

3 2 1
1 2

4

3 2 1
2 1

-1

Scoring

Subtask \(1\): \(M, N \leq 1000\)

Subtask \(2\): \(K \leq 2000\)

Subtask \(3\): Không có ràng buộc gì thêm