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×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≤x≤m,1≤y≤n) ~ mô tả phòng ~ (x,y) ~ có đặt công tắc và ~ k ~ tọa độ phòng là phân biệt.

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.

Ràng buộc

• Trong tất cả các test: ~ 2 ≤ m,n ≤10^5; 1≤ K ≤ 2×10^5 ~.
• Subtask 1: 30% số test tương ứng 30% số điểm của bài có ~ m,n ≤ 1000 ~;
• Subtask 2: 40% số test tương ứng 40% số điểm của bài có ~k ≤ 2000 ~;
• Subtask 3: Không có ràng buộc gì thêm.

Ví dụ:

Input 1

3 2 1 
1 2 

Output 1

4 

Input 2

3 2 1 
2 1 

Output 2

-1