Quân tượng

Xét bàn cờ vuông kích thước $n\times n$. Các dòng được đánh số từ $1$ đến $n$, từ dưới lên trên. Các cột được đánh số từ $1$ đến $n$ từ trái qua phải. Ô nằm trên giao của dòng $i$ và cột $j$ được gọi là ô $(i,j)$. Trên bàn cờ có $m$ ($0\le m\le n$) quân cờ. Với $m>0$, quân cờ thứ $i$ ở ô $(r_i,c_i)$, $i=1,2,\dots ,m$. Không có hai quân cờ nào ở trên cùng một ô. Trong số các ô còn lại của bàn cờ, tại ô $(p,q)$ có một quân tượng. Mỗi một nước đi, từ vị trí đang đứng quân tượng chỉ có thể di chuyển đến được những ô trên cùng đường chéo với nó mà trên đường đi không phải qua các ô đã có quân.

Cần phải đưa quân tượng từ ô xuất phát $(p,q)$ về ô đích $(s,t)$. Giả thiết là ở ô đích không có quân cờ. Nếu ngoài quân tượng không có quân nào khác trên bàn cờ thì chỉ có $2$ trường hợp: hoặc là không thể tới được ô đích, hoặc là tới được sau không quá $2$ nước đi. Khi trên bàn cờ còn có các quân cờ khác, vấn đề sẽ không còn đơn giản như vậy.

Yêu cầu: Cho kích thước bàn cờ $n$, số quân cờ hiện có trên bàn cờ $m$ và vị trí của chúng, ô xuất phát và ô đích của quân tượng. Hãy xác định số nước đi ít nhất cần thực hiện để đưa quân tượng về ô đích hoặc đưa ra số $-1$ nếu điều này không thể thực hiện được.

Dữ liệu vào

• Dòng đầu tiên chứa $6$ số nguyên $n$, $m$, $p$, $q$, $s$, $t$.
• Nếu $m>0$ thì mỗi dòng thứ $i$ trong $m$ dòng tiếp theo chứa một cặp số nguyên $r_i,c_i$ xác định vị trí quân thứ $i$.

Hai số liên tiếp trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra

Gồm $1$ dòng duy nhất là số nước đi tìm được.

Ràng buộc

• $1\le n\le 200$, $0\le m\le n$.
• $1\le p,q,s,t,r_i,c_i\le n$; ô $(p,q)$ và ô $(s,t)$ không có quân cờ.

Subtasks

• Subtask 1 ($60\%$ số test): $n\le 20$.
• Subtask 2 ($40\%$ số test): $20<n\le 200$.

Mỗi subtask gồm nhiều test, mỗi test được chấm điểm riêng.

Ví dụ