Đề bài
Bạn đã đi lạc vào một dinh thự rộng lớn. Dinh thự này có cấu trúc gồm các căn phòng hình vuông xếp thành dạng 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 có $M \times N$ căn phòng. Căn phòng nằm ở 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)$.
Giữa $2$ căn phòng liền kề theo hướng đông, tây, nam hoặc bắc được nối với nhau bởi một cánh cửa nằm ở chính giữa bức tường. Mỗi cánh cửa luôn ở một trong hai trạng thái: đóng (không thể đi qua) hoặc mở (có thể đi qua). Khi cánh cửa mở, mất $1$ phút để di chuyển giữa tâm của các căn phòng đó. Ngoài ra, ở tâm của một số căn phòng có một công tắc; nếu bạn nhấn giữ công tắc trong $1$ phút, trạng thái đóng/mở của tất cả các cánh cửa trong dinh thự sẽ đảo ngược.
Hiện tại, tất cả các cánh cửa nối $2$ căn phòng liền kề theo hướng đông - tây đều đang đóng, và tất cả các cánh cửa nối $2$ căn phòng liền kề theo hướng nam - bắc đều đang mở. Hiện bạn đang ở tâm của căn phòng $(1, 1)$, và bạn muốn di chuyển đến tâm của căn phòng $(M, N)$ trong thời gian ngắn nhất.
Yêu cầu
Cho biết kích thước $M, N$ của dinh thự và vị trí $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ của $K$ căn phòng có công tắc, hãy viết chương trình tìm số phút ít nhất cần thiết để di chuyển từ tâm căn phòng $(1, 1)$ đến tâm căn phòng $(M, N)$, bắt đầu từ trạng thái tất cả các cánh cửa nối $2$ căn phòng liền kề theo hướng đông - tây đều đóng và tất cả các cánh cửa nối $2$ căn phòng liền kề theo hướng nam - bắc đều mở. Tuy nhiên, nếu không thể đi đến căn phòng $(M, N)$, hãy chỉ rõ điều đó.
Giới hạn
- $2 \le M \le 100000$: số lượng căn phòng theo hướng đông - tây của dinh thự.
- $2 \le N \le 100000$: số lượng căn phòng theo hướng nam - bắc của dinh thự.
- $1 \le K \le 200000$: số lượng căn phòng có công tắc.
- $1 \le X_i \le M$: vị trí theo hướng đông - tây của căn phòng có công tắc.
- $1 \le Y_i \le N$: vị trí theo hướng nam - bắc của căn phòng có công tắc.
Dữ liệu vào
Đọc dữ liệu sau từ đầu vào chuẩn.
- Ở dòng $1$, ghi các số nguyên $M, N, K$ cách nhau bởi khoảng trắng. $M$ biểu thị số lượng căn phòng theo hướng đông - tây của dinh thự, $N$ biểu thị số lượng căn phòng theo hướng nam - bắc của dinh thự, và $K$ biểu thị số lượng căn phòng có công tắc.
- Ở dòng thứ $i$ ($1 \le i \le K$) trong $K$ dòng tiếp theo, ghi các số nguyên $X_i, Y_i$ cách nhau bởi khoảng trắng. Điều này biểu thị rằng có một công tắc ở tâm của căn phòng $(X_i, Y_i)$. $K$ cặp $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ đôi một khác nhau.
Kết quả
In ra đầu ra chuẩn trên $1$ dòng một số nguyên biểu thị số phút ít nhất cần thiết để di chuyển. Tuy nhiên, nếu không thể đi đến căn phòng $(M, N)$, hãy in ra số nguyên $-1$ để thay thế.
Tiêu chí chấm điểm
- Trong $20\%$ số điểm của dữ liệu chấm, thỏa mãn $M \le 1000$ và $N \le 1000$.
- Trong $30\%$ số điểm của dữ liệu chấm, thỏa mãn $K \le 2000$.
- Trong $50\%$ số điểm của dữ liệu chấm, thỏa mãn ít nhất một trong $2$ điều kiện trên. Ngoài ra, không có dữ liệu chấm nào thỏa mãn đồng thời cả $2$ điều kiện trên.
Ví dụ 1
Dữ liệu vào
3 2 1 1 2
Kết quả
4
Giải thích
Trong ví dụ này, bạn có thể di chuyển từ tâm căn phòng $(1, 1)$ đến tâm căn 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:
- Di chuyển đến tâm căn phòng $(1, 2)$.
- Nhấn công tắc ở tâm căn phòng $(1, 2)$.
- Di chuyển đến tâm căn phòng $(2, 2)$.
- Di chuyển đến tâm căn phòng $(3, 2)$.
Trạng thái của dinh thự khi đó được thể hiện trong hình dưới đây. Trong hình, hướng bên phải là hướng đông, hướng bên trên là hướng bắc, dấu $\times$ biểu thị vị trí của bạn, và dấu $\bigcirc$ biểu thị công tắc.
Ví dụ 2
Dữ liệu vào
3 2 1 2 1
Kết quả
-1
Giải thích
Trong ví dụ này, bạn không thể đi đến căn phòng $(3, 2)$.
Ví dụ 3
Dữ liệu vào
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
Kết quả
25
Giải thích
Trong ví dụ này, trạng thái ban đầu của dinh thự như hình dưới đây. Lưu ý rằng ở tâm căn phòng $(1, 1)$ hoặc căn phòng $(M, N)$ cũng có thể có công tắc.
