Bé Sen mới mua một căn 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ở thời gian đi 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)\).

Dữ liệu vào:

+ Dòng đầu tiên chứa 3 số nguyên \(m,n,k\)

+ Tiếp theo là \(k\) dòng, 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 và \(k\) tọa độ phòng là phân biệt.

Giới hạn:

+ Trong tất cả các test: \(2\ \leq \ m,n\ \leq 10^{5};\ 1 \leq \ K\ \leq \ 2 \times 10^{5}.\)

+ Subtask 1:​ 30% số test tương ứng 30% số điểm của bài có \(m,n\ \leq \ 1000;\)

+ Subtask 2:​ 40% số test tương ứng 40% số điểm của bài có \(k\ \leq \ 2000\);

+ Subtask 3:​ Không có ràng buộc gì thêm.

Kết quả: Ghi một số nguyên là 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\).

Ví dụ: