Death Knight

Interview

Time limit2sMemory limit512 MB

Summary

Find the minimum number of moves for a knight-like piece with six fixed moves to travel between two squares on an N by N board, or -1 if unreachable.

Level: Medium4 of 10
Topics: BFS, Graph, Shortest path, Simulation
Solved: No attempts yet

Statement

Cubelover, who loves games, created a new chess piece called the "death knight". If the death knight is at (r, c), it can move to (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1).

Given an N×N chessboard and two squares (r1, c1) and (r2, c2), find the minimum number of moves for the death knight to go from (r1, c1) to (r2, c2). Rows and columns of the board are numbered starting from 0.

The death knight cannot leave the board.

Input

The first line gives the size of the chessboard N (5 ≤ N ≤ 200). The second line gives r1, c1, r2, c2.

Output

On the first line, print the minimum number of moves for the death knight to go from (r1, c1) to (r2, c2). If it cannot move there, print -1.

Examples3

Example 1
Input
```
7
6 6 0 1
```
Expected output
```
4
```
Example 2
Input
```
6
5 1 0 5
```
Expected output
```
-1
```
Example 3
Input
```
7
0 3 4 3
```
Expected output
```
2
```