Minimum Knight Moves

You are given the starting and target positions of a knight on a standard 8×8 chessboard. The knight moves in an L-shape: it can move either two squares in one direction and then one square perpendicular, or one square in one direction and then two squares perpendicular. In other words, from a cell \((x, y)\), the knight can move to any cell \((x \pm 2, y \pm 1)\) or \((x \pm 1, y \pm 2)\), provided the destination remains within the chessboard.

Your task is to determine the minimum number of moves required for the knight to move from the starting position \((x_1, y_1)\) to the target position \((x_2, y_2)\). It is guaranteed that both positions are valid (i.e. between 1 and 8 for both coordinates).

Note: Use a breadth-first search (BFS) approach to solve this problem.

inputFormat

The input consists of a single line containing four space-separated integers: (x_1), (y_1), (x_2), (y_2), representing the starting and target coordinates of the knight on an 8×8 chessboard.

outputFormat

Output a single integer representing the minimum number of moves required for the knight to reach the target position from the starting position.## sample

1 1 1 1

0