Cho bàn cờ vua (cờ quốc tế) kích thước n x n. Tìm số bước đi ít nhất để một quân mã xuất phát ở ô (x1, y1) đi đến ô (x2, y2).

Dòng đầu là số nguyên dương n ( 6 ≤ n ≤ 9)

Dòng thứ 2 chứa 4 số nguyên x1, y1, x2, y2 (1 ≤ x1, y1, x2, y2 ≤ n)

Ghi ra số bước đi ít nhất.

Ví dụ:

Input

8
2 3 3 3

Output

3

Cho bàn cờ vua (cờ quốc tế) kích thước n x n. Tìm số bước đi ít nhất để một quân mã xuất phát ở ô (x1, y1) đi đến ô (x2, y2).

Dòng đầu là số nguyên dương n ( 6 ≤ n ≤ 1000)

Dòng thứ 2 chứa 4 số nguyên x1, y1, x2, y2 (1 ≤ x1, y1, x2, y2 ≤ n)

Ghi ra:

Dòng đầu là số bước đi ít nhất.

Các dòng tiếp theo: mỗi dòng ghi các ô đi qua, bắt đầu từ (x1, y1).

Ví dụ:

Input

8
2 3 3 3

Output

3
2 3
4 4
2 5
3 3

Cho bàn cờ vua (cờ quốc tế) kích thước n x n. Tìm hành trình để một quân mã xuất phát ở ô (x, y) và đi qua tất cả các ô, mỗi ô 1 lần.

Nhập vào số nguyên dương n ( 4 ≤ n ≤ 8) và 2 số nguyên x, y (1 ≤ x, y ≤ n) trên cùng 1 dòng

Ghi ra tọa độ các ô mà quân mã đi qua. Nếu có nhiều cách đi thì chỉ cần ghi ra 1 cách bất kì. Nếu không có cách đi nào thì ghi ra số -1.

Ví dụ:

Input

5 1 1

Output

1 1
2 3
3 1
1 2
2 4
4 5
5 3
4 1
2 2
1 4
3 5
5 4
4 2
2 1
1 3
2 5
3 3
5 2
4 4
3 2
5 1
4 3
5 5
3 4
1 5

Cho 4 phép biến đổi đối với số nguyên a:

• Tăng a thêm 1;
• Giảm a bớt 1;
• Nhân a cho 2;
• Chia a cho 2 (lấy phần nguyên); Cho 2 số nguyên dương a, b ≤ 1000. Hãy tìm ít phép biến đổi nhất để biến a thành b.

VD: a=7; b=16 ⇒ kq là 2; (cộng 1 → nhân 2)

VD2: a=7, b=12 ⇒ kq là 2; (trừ 1 rồi nhân 1)

Ví dụ:

Input

7
16

Output

2

Tài liệu tham khảo