현명한 나이트

$N\times N$ 크기 체스판의 특정한 위치에 나이트 하나가 있다. $M$개의 상대편 말의 위치가 주어질 때, 각 상대편 말을 잡기 위한 나이트의 최소 이동 수를 계산하는 프로그램을 작성하시오.

나이트는 일반적인 체스에서와 동일하게 이동한다. 현재 나이트의 위치가 $(X,Y)$일 때, 나이트는 다음 8개 위치 중 하나로 이동한다.

$(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)$

$N=5$일 때 나이트가 $(3,3)$에 있다면 이동 가능한 위치는 다음과 같다. 나이트가 있는 위치는 K, 이동 가능한 위치는 노란색으로 나타냈다.

예를 들어 $N=5$, $M=3$이고 나이트가 $(2,4)$에 있다고 하자. 상대편 말의 위치가 차례대로 $(3,2)$, $(3,5)$, $(4,5)$라면 각 상대편 말을 잡기 위한 최소 이동 수는 차례대로 1, 2, 1이 된다. 아래 그림에서 상대편 말의 위치는 E로 나타냈다. 이 문제에서 위치는 (행,열) 형태로 나타낸다.

첫째 줄에 $N$과 $M$이 공백을 기준으로 구분되어 자연수로 주어진다. ($1 \le N \le 500$, $1 \le M \le 1{,}000$) 둘째 줄에 나이트의 위치 $(X, Y)$를 나타내는 $X$와 $Y$가 공백을 기준으로 구분되어 자연수로 주어진다. ($1 \le X, Y \le N$) 셋째 줄부터 $M$개의 줄에 걸쳐 각 상대편 말의 위치 $(A, B)$를 나타내는 $A$와 $B$가 공백을 기준으로 구분되어 자연수로 주어진다. ($1 \le A, B \le N$)

입력으로 주어지는 모든 말의 위치는 중복되지 않으며, 나이트가 도달할 수 있는 위치로만 주어진다.

첫째 줄에 각 상대편 말을 잡기 위한 최소 이동 수를 공백을 기준으로 구분하여 출력한다.

출력할 때는 입력에서 상대편 말 정보가 주어진 순서에 맞게 차례대로 출력한다.