Thành phố của Okabe

Thành phố được mô tả bởi một lưới $n\times m$ ô. Các hàng được đánh số từ $1$ đến $n$ từ trên xuống dưới, các cột được đánh số từ $1$ đến $m$ từ trái sang phải. Trong thành phố có đúng $k$ ô được chiếu sáng sẵn bởi đèn đường, trong đó chắc chắn có ô góc trên bên trái $(1,1)$.

Okabe xuất phát từ ô $(1,1)$ và muốn tới ô $(n,m)$. Anh chỉ đi được trên những ô đang sáng, và mỗi bước chỉ di chuyển sang ô kề cạnh theo bốn hướng lên, xuống, trái, phải.

Ngoài ra, Okabe có thể trả $1$ đồng xu để thắp sáng tạm thời toàn bộ một hàng hoặc toàn bộ một cột tuỳ chọn, nhờ đó đi qua được cả những ô vốn không sáng. Tại mỗi thời điểm chỉ có nhiều nhất một hàng hoặc một cột được thắp sáng tạm thời. Muốn đổi sang hàng/cột khác, Okabe phải đang đứng trên một ô được chiếu sáng sẵn và trả thêm $1$ đồng xu. Ngay khi đổi, hàng/cột tạm thời cũ tắt trở lại: mọi ô trong đó không được chiếu sáng sẵn sẽ tối lại như cũ.

Hãy tìm số đồng xu ít nhất Okabe cần trả để đi từ $(1,1)$ tới $(n,m)$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$.
• $k$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $r_i$ và $c_i$ là hàng và cột của ô được chiếu sáng sẵn thứ $i$.

Các ô được chiếu sáng sẵn đôi một phân biệt, và ô $(1,1)$ chắc chắn nằm trong số đó. Lưu ý ô đích $(n,m)$ có thể không được chiếu sáng sẵn.

Dữ liệu ra

In ra một số nguyên duy nhất là số đồng xu ít nhất Okabe cần trả, hoặc $-1$ nếu không thể tới được ô $(n,m)$.

Ràng buộc

• $2\le n,m,k\le {10}^4$
• $1\le r_i\le n$, $1\le c_i\le m$

Ví dụ