Bạn đã đi lạc vào một dinh thự lớn. Dinh thự gồm các căn phòng hình vuông xếp thành lưới theo các hướng đông, tây, nam, bắc, với \(M\) cột theo hướng đông–tây và \(N\) hàng theo hướng nam–bắc, tổng cộng \(M\times N\) phòng. Phòng ở cột thứ \(x\) tính từ phía tây (\(1\le x\le M\)) và hàng thứ \(y\) tính từ phía nam (\(1\le y\le N\)) được ký hiệu là \((x,y)\).

Hai phòng kề nhau theo một trong bốn hướng được nối bằng một cánh cửa ở chính giữa bức tường chung. Mỗi cửa hoặc đóng và không thể đi qua, hoặc mở và có thể đi qua. Khi cửa mở, đi từ tâm phòng này đến tâm phòng kia mất \(1\) phút. Ngoài ra, ở tâm một số phòng có công tắc; nếu nhấn giữ công tắc trong \(1\) phút, trạng thái đóng/mở của tất cả cửa trong dinh thự sẽ đảo ngược.

Hiện tại, mọi cửa nối hai phòng kề nhau theo hướng đông–tây đều đóng, còn mọi cửa nối hai phòng kề nhau theo hướng nam–bắc đều mở. Bạn đang ở tâm phòng \((1,1)\) và muốn đến tâm phòng \((M,N)\) trong thời gian ngắn nhất.

Yêu cầu

Cho kích thước dinh thự \(M,N\) và vị trí của \(K\) phòng có công tắc là \((X_1,Y_1),(X_2,Y_2),\ldots,(X_K,Y_K)\), hãy viết chương trình tính số phút ít nhất cần thiết để đi từ tâm phòng \((1,1)\) đến tâm phòng \((M,N)\), bắt đầu với các cửa đông–tây đóng và các cửa nam–bắc mở. Nếu không thể đến phòng \((M,N)\), hãy báo điều đó.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa ba số nguyên \(M,N,K\), cách nhau bởi dấu cách. \(M\) là số phòng theo hướng đông–tây, \(N\) là số phòng theo hướng nam–bắc, \(K\) là số phòng có công tắc.
• Dòng thứ \(i\) trong \(K\) dòng tiếp theo (\(1\le i\le K\)) chứa hai số nguyên \(X_i,Y_i\), cách nhau bởi dấu cách, cho biết có công tắc ở tâm phòng \((X_i,Y_i)\).

Các cặp \((X_1,Y_1),(X_2,Y_2),\ldots,(X_K,Y_K)\) đôi một khác nhau.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên là thời gian di chuyển ngắn nhất, tính bằng phút. Nếu không thể đến phòng \((M,N)\), in ra số nguyên \(-1\).

Ràng buộc

• \(2\le M\le100000\).
• \(2\le N\le100000\).
• \(1\le K\le200000\).
• \(1\le X_i\le M\) (\(1\le i\le K\)).
• \(1\le Y_i\le N\) (\(1\le i\le K\)).

Phân nhóm

• \(20\%\) số điểm dành cho các dữ liệu thỏa mãn \(M\le1000\) và \(N\le1000\).
• \(30\%\) số điểm dành cho các dữ liệu thỏa mãn \(K\le2000\).
• \(50\%\) số điểm dành cho các dữ liệu thỏa mãn ít nhất một trong hai điều kiện trên. Không có dữ liệu chấm nào đồng thời thỏa mãn cả hai điều kiện.

3 2 1
1 2

4

Có thể đi từ tâm phòng \((1,1)\) đến tâm phòng \((3,2)\) trong \(4\) phút bằng các hành động sau, và đây là thời gian ngắn nhất:

1. Đi đến tâm phòng \((1,2)\).
2. Nhấn công tắc ở tâm phòng \((1,2)\).
3. Đi đến tâm phòng \((2,2)\).
4. Đi đến tâm phòng \((3,2)\).

3 2 1
2 1

-1

Trong ví dụ này, bạn không thể đến phòng \((3,2)\).

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

Trạng thái ban đầu của dinh thự trong ví dụ này được minh họa bên dưới. Lưu ý rằng tâm phòng \((1,1)\) hoặc phòng \((M,N)\) cũng có thể có công tắc.