Wise Knight

A single knight sits at a particular position on an $N\times N$ chessboard. Given the positions of $M$ opposing pieces, write a program that computes the minimum number of moves the knight needs to capture each opposing piece.

The knight moves as in ordinary chess. When the knight is at $(X,Y)$, it moves to one of the following eight positions.

$(X-2,Y-1)$, $(X-2,Y+1)$, $(X-1,Y-2)$, $(X-1,Y+2)$, $(X+1,Y-2)$, $(X+1,Y+2)$, $(X+2,Y-1)$, $(X+2,Y+1)$

When $N=5$ and the knight is at $(3,3)$, the reachable positions are shown below. The position of the knight is marked K, and reachable positions are shown in yellow.

For example, suppose $N=5$, $M=3$, and the knight is at $(2,4)$. If the opposing pieces are at $(3,2)$, $(3,5)$, and $(4,5)$ in that order, the minimum number of moves to capture them is 1, 2, and 1. In the figure below, the opposing pieces are marked E. Positions in this problem are written as (row, column).

The first line gives $N$ and $M$ as natural numbers separated by a space. ($1 \le N \le 500$, $1 \le M \le 1{,}000$) The second line gives $X$ and $Y$, the position $(X, Y)$ of the knight, as natural numbers separated by a space. ($1 \le X, Y \le N$) Each of the next $M$ lines gives $A$ and $B$, the position $(A, B)$ of an opposing piece, as natural numbers separated by a space. ($1 \le A, B \le N$)

All positions given in the input are distinct, and every one of them is a position the knight can reach.

On the first line, print the minimum number of moves needed to capture each opposing piece, separated by spaces.

Print them in the same order in which the opposing pieces were given in the input.