#1379. MANSION - Biệt thự

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 cột và hàng. Các cột được đánh số từ tới 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ừ tới theo chiều từ dưới lên trên (chiều hướng Nam đến Bắc). Biệt thự có phòng, phòng nằm trên cột hàng được ký hiệu là . 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 hai 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 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 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 tới phòng .

Dữ liệu vào:

• Dòng đầu tiên chứa ba số nguyên ;
• Tiếp theo là dòng, mỗi dòng gồm hai số nguyên mô tả phòng có đặt công tắc ( phòng có công tắc là phân biệt$.

Dữ liệu ra:

• Ghi ra một dòng chứa số nguyên là số phút ít nhất để đi từ phòng tới phòng . Nếu không đi được, in ra .

Ví dụ:

Dữ liệu vào:

3 2 1
1 2

Dữ liệu ra:

4

Dữ liệu vào:

3 2 1
2 1

Dữ liệu ra:

-1

Giải thích:

Giới hạn:

• Subtask số điểm của bài có ;
• Subtask số điểm của bài có ;
• Subtask số điểm còn lại không có ràng buộc gì thêm.