Given a square chessboard, the initial position of Knight and position of a target. Find out the minimum steps a Knight will take to reach the target position.
Note:
The initial and the target position coordinates of Knight have been given according to 1-base indexing.
 
Example 1:
Input:
N=6
knightPos[ ] = {4, 5}
targetPos[ ] = {1, 1}
Output:
3
Explanation:
Knight takes 3 step to reach from 
(4, 5) to (1, 1):
(4, 5) -> (5, 3) -> (3, 2) -> (1, 1).
 
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function minStepToReachTarget() which takes the initial position of Knight (KnightPos), the target position of Knight (TargetPos), and the size of the chessboard (N) as input parameters and returns the minimum number of steps required by the knight to reach from its current position to the given target position or return -1 if its not possible.
 
Expected Time Complexity: O(N^{2}).
Expected Auxiliary Space: O(N^{2}).
 
Constraints:
1 <= N <= 1000
1 <= Knight_pos(X, Y), Targer_pos(X, Y) <= N

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Graph algorithms

Graph traversal

Starter code: class Solution:



	#Function to find out minimum steps Knight needs to reach target position.

	def minStepToReachTarget(self, KnightPos, TargetPos, N):

		#Code here

Solutions:
class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		vis = [[-1] * (N + 1) for i in range(N + 1)]
		if KnightPos == TargetPos:
			return 0
		q = [(KnightPos[0], KnightPos[1], 0)]
		vis[KnightPos[0]][KnightPos[1]] = 0
		d = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [1, -2], [-1, -2], [-1, 2]]
		while q:
			(x, y, step) = q.pop(0)
			for (i, j) in d:
				r = x + i
				c = y + j
				if [r, c] == TargetPos:
					return step + 1
				if 0 <= r <= N and 0 <= c <= N and (vis[r][c] == -1):
					q.append([r, c, step + 1])
					vis[r][c] = step + 1
		return -1


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):

		class Cell:

			def __init__(self, x=0, y=0, dist=0):
				self.x = x
				self.y = y
				self.dist = dist

		def isInside(x, y, N):
			if x >= 1 and x <= N and (y >= 1) and (y <= N):
				return True
			return False
		dx = [2, 2, -2, -2, 1, 1, -1, -1]
		dy = [1, -1, 1, -1, 2, -2, 2, -2]
		queue = []
		queue.append(Cell(KnightPos[0], KnightPos[1], 0))
		visited = [[False for i in range(N + 1)] for j in range(N + 1)]
		visited[KnightPos[0]][KnightPos[1]] = True
		while len(queue) > 0:
			t = queue[0]
			queue.pop(0)
			if t.x == TargetPos[0] and t.y == TargetPos[1]:
				return t.dist
			for i in range(8):
				x = t.x + dx[i]
				y = t.y + dy[i]
				if isInside(x, y, N) and (not visited[x][y]):
					visited[x][y] = True
					queue.append(Cell(x, y, t.dist + 1))
		return -1


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		from collections import deque

		def isVisited(X, Y):
			return '{}_{}'.format(X, Y) in visitedCells
		moveDelta = ((2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2))
		dist = [[0 for i in range(N)] for j in range(N)]
		Q = deque()
		visitedCells = set()
		(xInit, yInit) = (KnightPos[0] - 1, KnightPos[1] - 1)
		(xFinal, yFinal) = (TargetPos[0] - 1, TargetPos[1] - 1)
		Q.append((xInit, yInit))
		visitedCells.add('{}_{}'.format(xInit, yInit))
		while Q:
			(xCur, yCur) = Q.popleft()
			if xCur == xFinal and yCur == yFinal:
				return dist[xCur][yCur]
			for (xDel, yDel) in moveDelta:
				(xNext, yNext) = (xCur + xDel, yCur + yDel)
				if 0 <= xNext < N and 0 <= yNext < N and (not isVisited(xNext, yNext)):
					dist[xNext][yNext] = dist[xCur][yCur] + 1
					visitedCells.add('{}_{}'.format(xNext, yNext))
					Q.append((xNext, yNext))
		return -1


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N) -> int:
		ans = 0
		dx = [-2, -1, 1, 2, -2, -1, 1, 2]
		dy = [-1, -2, -2, -1, 1, 2, 2, 1]
		q = deque()
		q.append(KnightPos)
		visited = set()
		visited.add(','.join(map(str, KnightPos)))
		while q:
			sz = len(q)
			while sz:
				sz -= 1
				cur = q.popleft()
				if cur == TargetPos:
					return ans
				for i in range(8):
					(nx, ny) = (cur[0] + dx[i], cur[1] + dy[i])
					nstr = ','.join(map(str, [nx, ny]))
					if nx > 0 and nx <= N and (ny > 0) and (ny <= N) and (nstr not in visited):
						visited.add(nstr)
						q.append([nx, ny])
			ans += 1
		return ans


from queue import Queue

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		q = Queue(maxsize=2 + N * N)
		vis = [[0 for i in range(N)] for j in range(N)]
		KnightPos[0] -= 1
		KnightPos[1] -= 1
		TargetPos[0] -= 1
		TargetPos[1] -= 1
		level = [[0 for i in range(N)] for j in range(N)]

		def ifpos(r, c):
			if not (r >= 0 and c >= 0 and (r < N) and (c < N)):
				return False
			elif vis[r][c] == 1:
				return False
			else:
				return True

		def bfs(kn):
			ops = [[-2, -1], [-2, 1], [2, -1], [2, 1], [-1, -2], [1, -2], [-1, 2], [1, 2]]
			q.put(kn)
			vis[kn[0]][kn[1]] = 1
			while not q.empty():
				(r, c) = q.get()
				if TargetPos == [r, c]:
					return level[r][c]
				else:
					for i in ops:
						if ifpos(r + i[0], c + i[1]):
							q.put([r + i[0], c + i[1]])
							vis[r + i[0]][c + i[1]] = 1
							level[r + i[0]][c + i[1]] = level[r][c] + 1
		ans = bfs(KnightPos)
		return ans


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		q = deque()
		q.append(KnightPos)
		distance = [[-1 for i in range(N + 1)] for j in range(N + 1)]
		visited = [[False for i in range(N + 1)] for j in range(N + 1)]
		distance[KnightPos[0]][KnightPos[1]] = 0
		while len(q) > 0:
			(pop_x, pop_y) = q.popleft()
			x = [-2, -2, -1, 1, 2, 2, 1, -1]
			y = [-1, 1, 2, 2, 1, -1, -2, -2]
			for i in range(8):
				x_val = x[i] + pop_x
				y_val = pop_y + y[i]
				if x_val > N or y_val > N or x_val <= 0 or (y_val <= 0) or (distance[x_val][y_val] != -1):
					continue
				distance[x_val][y_val] = 1 + distance[pop_x][pop_y]
				q.append([x_val, y_val])
		return distance[TargetPos[0]][TargetPos[1]]


from collections import *

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		kx = KnightPos[0] - 1
		ky = KnightPos[1] - 1
		tx = TargetPos[0] - 1
		ty = TargetPos[1] - 1
		ans = 0

		def isvalid(x, y, visit, N):
			if x >= 0 and y >= 0 and (x < N) and (y < N) and (visit[x][y] == False):
				return True
			return False
		if kx == tx and ty == ky:
			return ans
		moves = [[-1, 2], [-2, 1], [-2, -1], [-1, -2], [1, -2], [2, -1], [2, 1], [1, 2]]
		visit = [[False for i in range(N)] for j in range(N)]
		q = deque([[kx, ky]])
		visit[kx][ky] = True
		while q:
			ans += 1
			size = len(q)
			for i in range(size):
				(kx, ky) = q.popleft()
				for (m, n) in moves:
					if kx + m == tx and ky + n == ty:
						return ans
					if isvalid(kx + m, ky + n, visit, N):
						visit[kx + m][ky + n] = True
						q.append([kx + m, ky + n])
		return ans


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		vis = [[0] * N for i in range(N)]
		direc = [[1, 2], [2, 1], [-1, 2], [-2, 1], [-1, -2], [-2, -1], [1, -2], [2, -1]]

		def bfs(i, j, s):
			q = [[i, j, s]]
			while q:
				(t1, t2, d) = q.pop(0)
				if t1 == TargetPos[0] - 1 and t2 == TargetPos[1] - 1:
					return d
				for i in range(len(direc)):
					(t3, t4) = direc[i]
					if 0 <= t1 + t3 < N and 0 <= t2 + t4 < N and (vis[t1 + t3][t2 + t4] == 0):
						vis[t1 + t3][t2 + t4] = 1
						q.append([t1 + t3, t2 + t4, d + 1])
			return -1
		return bfs(KnightPos[0] - 1, KnightPos[1] - 1, 0)


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		que = []
		visited = []
		ww = KnightPos[0]
		ww1 = KnightPos[1]
		for i in range(0, N + 1):
			ax = [False] * (N + 1)
			visited.append(ax)
		que.append([KnightPos[0], KnightPos[1], 0])
		visited[ww][ww1]
		visited
		anss = 1000000
		row = [-1, -2, -2, -1, 1, 2, 2, 1]
		col = [-2, -1, 1, 2, 2, 1, -1, -2]
		final = TargetPos[0]
		final1 = TargetPos[1]
		while len(que) != 0:
			a = que[0][0]
			b = que[0][1]
			c = que[0][2]
			que.pop(0)
			if a == final and b == final1 and (c < anss):
				anss = c
			for i in range(0, 8):
				finrow = a + row[i]
				fincol = b + col[i]
				if finrow > 0 and finrow < N + 1 and (fincol > 0) and (fincol < N + 1) and (visited[finrow][fincol] == False):
					que.append([finrow, fincol, c + 1])
					visited[finrow][fincol] = True
		return anss


class QueueNode:

	def __init__(self, x, y, d=0):
		self.x = x
		self.y = y
		self.d = d

def isValid(i, j, N, M):
	return i >= 1 and i <= N and (j >= 1) and (j <= M)

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		M = N
		(i, j) = KnightPos
		(X, Y) = TargetPos
		visited = [[False for _ in range(M + 1)] for _ in range(N + 1)]
		start = QueueNode(i, j)
		visited[i][j] = True
		q = [start]
		dirj = [-1, -2, -2, -1, 1, 2, 2, 1]
		diri = [-2, -1, 1, 2, 2, 1, -1, -2]
		while len(q) != 0:
			curr = q.pop(0)
			(x, y, d) = (curr.x, curr.y, curr.d)
			if x == X and y == Y:
				return d
			for k in range(8):
				nexti = x + diri[k]
				nextj = y + dirj[k]
				if isValid(nexti, nextj, N, M) and (not visited[nexti][nextj]):
					q.append(QueueNode(nexti, nextj, d + 1))
					visited[nexti][nextj] = True
		return -1


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		(r, c) = (KnightPos[0] - 1, KnightPos[1] - 1)
		q = [(r, c, 0)]
		visited = set()
		visited.add((r, c))
		row = [-2, -2, -1, -1, 1, 1, 2, 2]
		col = [-1, 1, -2, 2, -2, 2, -1, 1]
		while q:
			(r, c, move) = q.pop(0)
			if r == TargetPos[0] - 1 and c == TargetPos[1] - 1:
				return move
			for i in range(len(row)):
				nextr = r + row[i]
				nextc = c + col[i]
				if (nextr, nextc) not in visited and nextr >= 0 and (nextc >= 0) and (nextr < N) and (nextc < N):
					visited.add((nextr, nextc))
					q.append((nextr, nextc, move + 1))


import sys

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		row = [-2, -2, 2, 2, 1, 1, -1, -1]
		col = [-1, 1, -1, 1, -2, 2, 2, -2]
		(sr, sc) = (KnightPos[0] - 1, KnightPos[1] - 1)
		(tr, tc) = (TargetPos[0] - 1, TargetPos[1] - 1)
		vis = set()
		vis.add((sr, sc))
		dis = 0
		q = [(sr, sc, dis)]
		while q:
			(sr, sc, dis) = q.pop(0)
			if sr == tr and sc == tc:
				return dis
			for i in range(8):
				nr = sr + row[i]
				nc = sc + col[i]
				if nr >= 0 and nc >= 0 and (nr < N) and (nc < N) and ((nr, nc) not in vis):
					vis.add((nr, nc))
					q.append((nr, nc, dis + 1))
		return dis


def shortest_path(source_pos, target_pos, n):
	board_arr = [[0] * n for i in range(n)]
	source_row = n - source_pos[1]
	source_col = source_pos[0] - 1
	target_row = n - target_pos[1]
	target_col = target_pos[0] - 1
	if source_row == target_row and source_col == target_col:
		return 0
	data_queue = [[source_row, source_col]]
	move_x = [2, 2, 1, 1, -1, -1, -2, -2]
	move_y = [1, -1, 2, -2, 2, -2, 1, -1]
	while len(data_queue) > 0:
		data = data_queue.pop(0)
		row = data[0]
		col = data[1]
		for i in range(8):
			new_row = row + move_y[i]
			new_col = col + move_x[i]
			if is_safe(board_arr, n, new_row, new_col, source_row, source_col):
				board_arr[new_row][new_col] = board_arr[row][col] + 1
				data_queue.append([new_row, new_col])
	return board_arr[target_row][target_col]

def is_safe(board_arr: [[]], n, row, col, source_row, source_col):
	if row == source_row and col == source_col:
		return False
	if row < 0 or row >= n:
		return False
	if col < 0 or col >= n:
		return False
	if board_arr[row][col] != 0:
		return False
	return True

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		return shortest_path(KnightPos, TargetPos, N)


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):

		def isValid(x, y, n):
			if x >= 0 and x < n and (y >= 0) and (y < n):
				return True
			return False
		queue = []
		tpos = [TargetPos[0] - 1, TargetPos[1] - 1]
		kpos = [KnightPos[0] - 1, KnightPos[1] - 1]
		visited = [[False for i in range(N)] for i in range(N)]
		queue.append(kpos)
		queue.append('END')
		visited[kpos[0]][kpos[1]] = True
		ans = 0
		while len(queue) > 0:
			if queue[0] == 'END':
				queue.pop(0)
				ans += 1
				if len(queue) > 0:
					queue.append('END')
			elif queue[0] == tpos:
				return ans
			else:
				temp = queue.pop(0)
				x = [1, 2, 2, 1, -1, -2, -2, -1]
				y = [2, 1, -1, -2, -2, -1, 1, 2]
				for i in range(8):
					if isValid(temp[0] + x[i], temp[1] + y[i], N) and visited[temp[0] + x[i]][temp[1] + y[i]] == False:
						if [temp[0] + x[i], temp[1] + y[i]] == tpos:
							return ans + 1
						else:
							queue.append([temp[0] + x[i], temp[1] + y[i]])
							visited[temp[0] + x[i]][temp[1] + y[i]] = True
		return ans


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		q = [(*KnightPos, 0)]
		visited = {tuple(KnightPos)}
		dx = [2, 2, -2, -2, 1, 1, -1, -1]
		dy = [1, -1, 1, -1, 2, -2, 2, -2]
		while len(q):
			q2 = []
			for (x, y, d) in q:
				if TargetPos == [x, y]:
					return d
				for i in range(8):
					xx = x + dx[i]
					yy = y + dy[i]
					if (xx, yy) not in visited:
						visited.add((xx, yy))
						q2.append((xx, yy, d + 1))
			q = q2
		return -1


class Solution:

	def minStepToReachTarget(self, kpos, tpos, n):
		vis = set()
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if kpos[0] == i and kpos[1] == j:
					q = []
					steps = 0
					q.append((i, j, steps))
					vis.add((i, j))
					while q:
						(row, col, c) = q.pop(0)
						if row == tpos[0] and col == tpos[1]:
							return c
						else:
							for (r, c1) in [[-1, 2], [-1, -2], [1, 2], [1, -2], [-2, -1], [-2, 1], [2, -1], [2, 1]]:
								nrow = r + row
								ncol = c1 + col
								if 1 <= nrow < n + 1 and 1 <= ncol < n + 1 and ((nrow, ncol) not in vis):
									q.append((nrow, ncol, c + 1))
									vis.add((nrow, ncol))


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		if KnightPos == TargetPos:
			return 0
		q = []
		q.append((KnightPos[0] - 1, KnightPos[1] - 1))
		dr = [1, 2, 1, 2, -1, -2, -1, -2]
		dc = [2, 1, -2, -1, -2, -1, 2, 1]
		visited = set()
		moves = 0
		while q:
			count = len(q)
			moves += 1
			while count:
				curr = q.pop(0)
				for i in range(8):
					r = curr[0] + dr[i]
					c = curr[1] + dc[i]
					if r < 0 or c < 0 or r >= N or (c >= N):
						continue
					if (r, c) in visited:
						continue
					if r == TargetPos[0] - 1 and c == TargetPos[1] - 1:
						return moves
					q.append((r, c))
					visited.add((r, c))
				count -= 1
		return -1


class Solution:

	def __init__(self):
		self.dis = 0

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		row = [-2, -2, 2, 2, 1, 1, -1, -1]
		col = [-1, 1, -1, 1, -2, 2, 2, -2]
		(sr, sc) = (KnightPos[0] - 1, KnightPos[1] - 1)
		(tr, tc) = (TargetPos[0] - 1, TargetPos[1] - 1)
		(rows, cols) = (N, N)
		vis = [[0 for i in range(N)] for j in range(N)]
		vis[sr][sc] = 1
		dis = 0
		q = [(sr, sc, dis)]
		while q:
			(sr, sc, dis) = q.pop(0)
			if sr == tr and sc == tc:
				return dis
			for i in range(8):
				nr = sr + row[i]
				nc = sc + col[i]
				if nr >= 0 and nc >= 0 and (nr < rows) and (nc < cols) and (vis[nr][nc] == 0):
					vis[nr][nc] = 1
					q.append((nr, nc, dis + 1))
		return dis


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		visited = [[False for _ in range(N)] for _ in range(N)]
		d = [[-1 for _ in range(N)] for _ in range(N)]
		visited[N - KnightPos[1]][KnightPos[0] - 1] = True
		d[N - KnightPos[1]][KnightPos[0] - 1] = 0
		Q = deque()
		Q.append((N - KnightPos[1], KnightPos[0] - 1))
		while Q:
			(i, j) = Q.popleft()
			for (u, w) in [(-2, -1), (-1, -2), (-2, 1), (-1, 2), (1, -2), (2, -1), (2, 1), (1, 2)]:
				if 0 <= i + u < N and 0 <= j + w < N:
					if not visited[i + u][j + w]:
						visited[i + u][j + w] = True
						d[i + u][j + w] = d[i][j] + 1
						Q.append((i + u, j + w))
		return d[N - TargetPos[1]][TargetPos[0] - 1]


from queue import Queue

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):

		def isval(a, b, N, visited):
			return a >= 0 and a < N and (b >= 0) and (b < N) and (visited[a][b] == False)
		direction = [[1, 2], [2, 1], [-1, 2], [-2, 1], [-1, -2], [-2, -1], [1, -2], [2, -1]]
		ta = TargetPos[0] - 1
		tb = TargetPos[1] - 1
		a = KnightPos[0] - 1
		b = KnightPos[1] - 1
		if ta == a and tb == b:
			return 0
		visited = []
		for i in range(N):
			visited.append([False for i in range(N)])
		q = Queue()
		q.put([a, b, 0])
		visited[a][b] = True
		while not q.empty():
			(a, b, d) = q.get()
			if a == ta and b == tb:
				return d
			for (u, v) in direction:
				m = a + u
				n = b + v
				if isval(m, n, N, visited):
					q.put([m, n, d + 1])
					visited[m][n] = True
		return -1


class Solution:

	def isvalid(self, i, j, n, visited):
		return i >= 0 and j >= 0 and (i < n) and (j < n) and (visited[i][j] == False)

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		from collections import deque
		q = deque()
		visited = [[False for i in range(N)] for j in range(N)]
		q.append([KnightPos[0] - 1, KnightPos[1] - 1, 0])
		visited[KnightPos[0] - 1][KnightPos[1] - 1] = True
		step = 1
		row = [2, -2, 2, -2, 1, -1, 1, -1]
		col = [1, -1, -1, 1, 2, -2, -2, 2]
		while len(q) > 0:
			node = q.popleft()
			if node[0] == TargetPos[0] - 1 and node[1] == TargetPos[1] - 1:
				return node[2]
			for i in range(8):
				nrow = node[0] + row[i]
				ncol = node[1] + col[i]
				if self.isvalid(nrow, ncol, N, visited):
					visited[nrow][ncol] = True
					q.append([nrow, ncol, node[2] + 1])
		return -1


from queue import Queue

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):

		def isValid(x, y, N, visited):
			return x >= 0 and x < N and (y >= 0) and (y < N) and (visited[x][y] == False)
		direc = [[1, 2], [2, 1], [-1, 2], [-2, 1], [-1, -2], [-2, -1], [1, -2], [2, -1]]
		tx = TargetPos[0] - 1
		ty = TargetPos[1] - 1
		x = KnightPos[0] - 1
		y = KnightPos[1] - 1
		if tx == x and ty == y:
			return 0
		visited = []
		for i in range(N):
			visited.append([False for i in range(N)])
		q = Queue()
		q.put([x, y, 0])
		visited[x][y] = True
		while not q.empty():
			(x, y, d) = q.get()
			if x == tx and y == ty:
				return d
			for (u, v) in direc:
				p = x + u
				r = y + v
				if isValid(p, r, N, visited):
					q.put([p, r, d + 1])
					visited[p][r] = True
		return -1


import numpy as np

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		visitedpos = []
		steps = []
		visitedpos.append(KnightPos)
		steps.append(0)
		visited = np.zeros([N + 1, N + 1])
		mina = N + 1
		while len(visitedpos) > 0:
			curr = visitedpos.pop(0)
			(curr_x, curr_y) = (curr[0], curr[1])
			curr_step = steps.pop(0)
			if curr_x == TargetPos[0] and curr_y == TargetPos[1]:
				mina = min(mina, curr_step)
			if curr_x + 2 < N + 1 and curr_y + 1 < N + 1 and (visited[curr_x + 2, curr_y + 1] == 0):
				visitedpos.append([curr_x + 2, curr_y + 1])
				visited[curr_x + 2, curr_y + 1] = 1
				steps.append(curr_step + 1)
			if curr_x + 2 < N + 1 and curr_y - 1 > 0 and (visited[curr_x + 2, curr_y - 1] == 0):
				visitedpos.append([curr_x + 2, curr_y - 1])
				visited[curr_x + 2, curr_y - 1] = 1
				steps.append(curr_step + 1)
			if curr_x - 2 > 0 and curr_y + 1 < N + 1 and (visited[curr_x - 2][curr_y + 1] == 0):
				visitedpos.append([curr_x - 2, curr_y + 1])
				visited[curr_x - 2, curr_y + 1] = 1
				steps.append(curr_step + 1)
			if curr_x - 2 > 0 and curr_y - 1 > 0 and (visited[curr_x - 2][curr_y - 1] == 0):
				visitedpos.append([curr_x - 2, curr_y - 1])
				visited[curr_x - 2, curr_y - 1] = 1
				steps.append(curr_step + 1)
			if curr_x + 1 < N + 1 and curr_y + 2 < N + 1 and (visited[curr_x + 1][curr_y + 2] == 0):
				visitedpos.append([curr_x + 1, curr_y + 2])
				visited[curr_x + 1, curr_y + 2] = 1
				steps.append(curr_step + 1)
			if curr_x + 1 < N + 1 and curr_y - 2 > 0 and (visited[curr_x + 1][curr_y - 2] == 0):
				visitedpos.append([curr_x + 1, curr_y - 2])
				visited[curr_x + 1, curr_y - 2] = 1
				steps.append(curr_step + 1)
			if curr_x - 1 > 0 and curr_y + 2 < N + 1 and (visited[curr_x - 1][curr_y + 2] == 0):
				visitedpos.append([curr_x - 1, curr_y + 2])
				visited[curr_x - 1, curr_y + 2] = 1
				steps.append(curr_step + 1)
			if curr_x - 1 > 0 and curr_y - 2 > 0 and (visited[curr_x - 1][curr_y - 2] == 0):
				visitedpos.append([curr_x - 1, curr_y - 2])
				visited[curr_x - 1, curr_y - 2] = 1
				steps.append(curr_step + 1)
		return mina


from collections import deque

class Solution:

	def isValid(self, i, j, N):
		if i > 0 and j > 0 and (i <= N) and (j <= N):
			return True
		return False

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		q = deque()
		vis = [[0] * (N + 1) for _ in range(N + 1)]
		dr = [-2, -2, -1, -1, 1, 1, 2, 2]
		dc = [1, -1, 2, -2, 2, -2, 1, -1]
		q.append([KnightPos[0], KnightPos[1], 0])
		vis[KnightPos[0]][KnightPos[1]] = 1
		while len(q) != 0:
			(i, j, steps) = q.popleft()
			if TargetPos[0] == i and TargetPos[1] == j:
				return steps
			for k in range(0, 8):
				ni = i + dr[k]
				nj = j + dc[k]
				if self.isValid(ni, nj, N) and vis[ni][nj] == 0:
					vis[ni][nj] = 1
					q.append([ni, nj, steps + 1])
		return -1


import math
from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		grid = [[0 for i in range(N)] for j in range(N)]
		m = N
		n = N
		i = KnightPos[1] - 1
		j = KnightPos[0] - 1
		grid[i][j] = 1
		q = deque()
		q.append([i, j])
		i = TargetPos[1] - 1
		j = TargetPos[0] - 1
		grid[i][j] = -1
		count = 0
		while len(q) != 0:
			temp_q = deque()
			while len(q) != 0:
				idx = q.popleft()
				i = idx[0]
				j = idx[1]
				if i - 2 >= 0:
					if j - 1 >= 0:
						if grid[i - 2][j - 1] == -1:
							return count + 1
						elif grid[i - 2][j - 1] == 0:
							grid[i - 2][j - 1] = 1
							temp_q.append([i - 2, j - 1])
					if j + 1 < n:
						if grid[i - 2][j + 1] == -1:
							return count + 1
						elif grid[i - 2][j + 1] == 0:
							grid[i - 2][j + 1] = 1
							temp_q.append([i - 2, j + 1])
				if j - 2 >= 0:
					if i - 1 >= 0:
						if grid[i - 1][j - 2] == -1:
							return count + 1
						elif grid[i - 1][j - 2] == 0:
							grid[i - 1][j - 2] = 1
							temp_q.append([i - 1, j - 2])
					if i + 1 < m:
						if grid[i + 1][j - 2] == -1:
							return count + 1
						elif grid[i + 1][j - 2] == 0:
							grid[i + 1][j - 2] = 1
							temp_q.append([i + 1, j - 2])
				if i + 2 < m:
					if j - 1 >= 0:
						if grid[i + 2][j - 1] == -1:
							return count + 1
						elif grid[i + 2][j - 1] == 0:
							grid[i + 2][j - 1] = 1
							temp_q.append([i + 2, j - 1])
					if j + 1 < n:
						if grid[i + 2][j + 1] == -1:
							return count + 1
						elif grid[i + 2][j + 1] == 0:
							grid[i + 2][j + 1] = 1
							temp_q.append([i + 2, j + 1])
				if j + 2 < n:
					if i - 1 >= 0:
						if grid[i - 1][j + 2] == -1:
							return count + 1
						elif grid[i - 1][j + 2] == 0:
							grid[i - 1][j + 2] = 1
							temp_q.append([i - 1, j + 2])
					if i + 1 < m:
						if grid[i + 1][j + 2] == -1:
							return count + 1
						elif grid[i + 1][j + 2] == 0:
							grid[i + 1][j + 2] = 1
							temp_q.append([i + 1, j + 2])
			q = temp_q.copy()
			count += 1
		return 0


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		if KnightPos == TargetPos:
			return 0
		q = deque([])
		visited = set()
		minSteps = 0
		(r1, c1) = KnightPos
		q.append((r1, c1))
		visited.add((r1, c1))
		while q:
			for i in range(len(q)):
				(r, c) = q.popleft()
				directions = [[r - 1, c + 2], [r + 1, c + 2], [r - 1, c - 2], [r + 1, c - 2], [r - 2, c + 1], [r - 2, c - 1], [r + 2, c + 1], [r + 2, c - 1]]
				for (nr, nc) in directions:
					if 1 <= nr <= N and 1 <= nc <= N and ((nr, nc) not in visited):
						if nr == TargetPos[0] and nc == TargetPos[1]:
							return minSteps + 1
						q.append((nr, nc))
						visited.add((nr, nc))
			minSteps += 1
		return -1


from collections import deque

class Solution:

	def check(self, N, x, y):
		if 0 <= x < N and 0 <= y < N:
			return True
		return False

	def explore(self, target, pos, N, dis_x, dis_y, vis):
		q = deque()
		q.append(pos)
		while len(q) != 0:
			a = q.popleft()
			for i in range(8):
				(new_x, new_y) = (a[0] + dis_x[i], a[1] + dis_y[i])
				if self.check(N, new_x, new_y):
					if vis[new_x][new_y] == 0:
						vis[new_x][new_y] = vis[a[0]][a[1]] + 1
						q.append([new_x, new_y])
					elif vis[new_x][new_y] > vis[a[0]][a[1]] + 1:
						vis[new_x][new_y] = vis[a[0]][a[1]] + 1
						q.append([new_x, new_y])
		return vis[target[0]][target[1]]

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		dis_x = [1, -1, 1, -1, -2, -2, 2, 2]
		dis_y = [2, 2, -2, -2, 1, -1, -1, 1]
		vis = [[0 for i in range(N)] for j in range(N)]
		KnightPos = [KnightPos[0] - 1, KnightPos[1] - 1]
		TargetPos = [TargetPos[0] - 1, TargetPos[1] - 1]
		vis[KnightPos[0]][KnightPos[1]] = 0
		a = self.explore(TargetPos, KnightPos, N, dis_x, dis_y, vis)
		return a


class Cell:

	def __init__(self, x=0, y=0, dist=0):
		self.x = x
		self.y = y
		self.dist = dist

class Solution:

	def isInside(self, x, y, N):
		if x >= 1 and x <= N and (y >= 1) and (y <= N):
			return True
		return False

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		(tx, ty) = (TargetPos[0] - 1, TargetPos[1] - 1)
		(x1, y1) = (KnightPos[0] - 1, KnightPos[1] - 1)
		if x1 == tx and y1 == ty:
			return 0
		visited = [[0 for j in range(N)] for i in range(N)]
		queue = []
		queue.append([x1, y1])
		visited[x1][y1] = 1
		step = 0
		directions = [[1, 2], [1, -2], [-1, 2], [-1, -2], [2, 1], [-2, 1], [2, -1], [-2, -1]]
		while queue:
			step += 1
			for i in range(len(queue)):
				(X, Y) = queue.pop(0)
				for (dx, dy) in directions:
					x = X + dx
					y = Y + dy
					if x == tx and y == ty:
						return step
					if x >= 0 and x < N and (y >= 0) and (y < N) and (visited[x][y] == 0):
						visited[x][y] = 1
						queue.append([x, y])
		return step if step > 0 else -1


class Solution:

	def minStepToReachTarget(self, kpos, tpos, n):

		def bfs(i, j, vis, tpos, steps):
			q = []
			q.append((i, j, steps))
			vis.add((i, j))
			while q:
				(r, c, st) = q.pop(0)
				if tpos[0] == r and tpos[1] == c:
					return st
				else:
					for (i, j) in [[-1, 2], [-1, -2], [1, 2], [1, -2], [-2, -1], [-2, 1], [2, -1], [2, 1]]:
						(nrow, ncol) = (r + i, j + c)
						if 1 <= nrow < n + 1 and 1 <= ncol < n + 1 and ((nrow, ncol) not in vis):
							q.append((nrow, ncol, st + 1))
							vis.add((nrow, ncol))
		vis = set()
		steps = 0
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if kpos[0] == i and kpos[1] == j:
					ans = bfs(i, j, vis, tpos, 0)
		return ans


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		from collections import deque
		n = N
		visited = [[False for i in range(n)] for j in range(n)]
		dr = [1, 2, 2, 1, -1, -2, -2, -1]
		dc = [-2, -1, 1, 2, 2, 1, -1, -2]

		def bfs(row, col):
			q = deque()
			q.append((row, col, 0))
			visited[row][col] = True
			while q:
				(row, col, d) = q.popleft()
				if row == TargetPos[0] - 1 and col == TargetPos[1] - 1:
					return d
				for i in range(8):
					r = row + dr[i]
					c = col + dc[i]
					if r >= 0 and r < n and (c >= 0) and (c < n) and (not visited[r][c]):
						q.append((r, c, d + 1))
						visited[r][c] = True
			return -1
		return bfs(KnightPos[0] - 1, KnightPos[1] - 1)


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, n):
		start = (KnightPos[0] - 1, KnightPos[1] - 1)
		target = (TargetPos[0] - 1, TargetPos[1] - 1)
		moves = [(2, 1), (1, 2), (-2, 1), (-1, 2), (2, -1), (1, -2), (-2, -1), (-1, -2)]
		q = deque([(start, 0)])
		visited = set([start])
		while q:
			(cur, steps) = q.popleft()
			if cur == target:
				return steps
			for move in moves:
				next_pos = (cur[0] + move[0], cur[1] + move[1])
				if next_pos[0] >= 0 and next_pos[0] < n and (next_pos[1] >= 0) and (next_pos[1] < n) and (next_pos not in visited):
					visited.add(next_pos)
					q.append((next_pos, steps + 1))
		return -1


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		visited = [[False] * (N + 1) for _ in range(N + 1)]
		dire = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [-1, 2], [1, -2], [-1, -2]]
		queue = []
		row = KnightPos[0]
		col = KnightPos[1]
		queue.append([row, col, 0])
		visited[row][col] = True

		def valid(tmp, n, m):
			if tmp[0] <= 0 or tmp[1] <= 0 or tmp[0] > n or (tmp[1] > m):
				return False
			else:
				return True
		while len(queue) > 0:
			tmp = queue.pop(0)
			if tmp[0] == TargetPos[0] and tmp[1] == TargetPos[1]:
				return tmp[2]
			for e in dire:
				nex = [tmp[0] + e[0], tmp[1] + e[1], tmp[2] + 1]
				if not valid(nex, N, N):
					continue
				if not visited[nex[0]][nex[1]]:
					visited[nex[0]][nex[1]] = True
					queue.append(nex)


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		q = deque()
		KnightPos[0] -= 1
		KnightPos[1] -= 1
		TargetPos[0] -= 1
		TargetPos[1] -= 1
		if KnightPos == TargetPos:
			return 0
		q.appendleft((KnightPos[0], KnightPos[1], 0))
		vis = set()
		vis.add((KnightPos[0], KnightPos[1]))
		dictio = {(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)}
		vis = set()
		while q:
			(r, c, steps) = q.pop()
			for (di, dj) in dictio:
				(n_i, n_j) = (r + di, c + dj)
				if n_i >= 0 and n_j >= 0 and (n_i < N) and (n_j < N) and ((n_i, n_j) not in vis):
					if [n_i, n_j] == TargetPos:
						return steps + 1
					vis.add((n_i, n_j))
					q.appendleft((n_i, n_j, steps + 1))
		return -1


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		lis = [[KnightPos[0], KnightPos[1], 0]]
		count = 0
		pos = [[-2, -1], [-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2], [-1, -2]]
		vis = {}
		while lis:
			(r, c, ctr) = lis.pop(0)
			if r == TargetPos[0] and c == TargetPos[1]:
				return ctr
			vis[r, c] = 1
			for (i, j) in pos:
				R = r + i
				C = c + j
				if R >= 1 and R <= N and (C >= 1) and (C <= N) and ((R, C) not in vis):
					lis.append([R, C, ctr + 1])
					vis[R, C] = 1
		return -1


from queue import Queue

class Solution:

	def isValid(self, i, j, N, visited):
		if i < 0 or j < 0 or i >= N or (j >= N) or (visited[i][j] == True):
			return False
		return True

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		KnightPos[0] -= 1
		KnightPos[1] -= 1
		TargetPos[0] -= 1
		TargetPos[1] -= 1
		visited = [[False for j in range(N)] for i in range(N)]
		q = Queue()
		q.put([KnightPos[0], KnightPos[1]])
		visited[KnightPos[0]][KnightPos[1]] = True
		dx = [-2, -2, -1, 1, 2, 2, 1, -1]
		dy = [-1, 1, 2, 2, 1, -1, -2, -2]
		moves = 0
		while q.qsize() > 0:
			currsize = q.qsize()
			for _ in range(currsize):
				temp = q.get()
				i = temp[0]
				j = temp[1]
				if i == TargetPos[0] and j == TargetPos[1]:
					return moves
				for indx in range(8):
					x = dx[indx] + i
					y = dy[indx] + j
					if self.isValid(x, y, N, visited) == True:
						q.put([x, y])
						visited[x][y] = True
			moves += 1
		return -1


from collections import deque

class Solution:
	ans = float('inf')

	def minStepToReachTarget(self, src, des, N):
		(a, b) = src
		cnt = 0
		visited = [[0 for _ in range(N)] for _ in range(N)]
		return self.bfs(a - 1, b - 1, des, visited, N, cnt)

	def bfs(self, a, b, des, visited, N, cnt):
		visited[a][b] == 1
		queue = deque()
		queue.append((a, b, cnt))
		while queue:
			(x, y, cnt) = queue.popleft()
			if x == des[0] - 1 and y == des[1] - 1:
				return cnt
			dx = [-2, -1, 1, 2, -2, -1, 1, 2]
			dy = [-1, -2, -2, -1, 1, 2, 2, 1]
			for j in range(8):
				new_x = x + dx[j]
				new_y = y + dy[j]
				if new_x >= 0 and new_y >= 0 and (new_x < N) and (new_y < N) and (visited[new_x][new_y] == 0):
					visited[new_x][new_y] = 1
					queue.append((new_x, new_y, cnt + 1))
		return -1


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		vis = [[0 for i in range(N)] for j in range(N)]
		roww = [-2, -2, 2, 2, 1, -1, 1, -1]
		coll = [-1, 1, -1, 1, -2, -2, 2, 2]
		(start_row, start_col) = (KnightPos[0] - 1, KnightPos[1] - 1)
		(target_row, target_col) = (TargetPos[0] - 1, TargetPos[1] - 1)
		visited = [[False for _ in range(N)] for _ in range(N)]
		visited[start_row][start_col] = True
		queue = [(start_row, start_col, 0)]
		while queue:
			(row, col, dist) = queue.pop(0)
			if row == target_row and col == target_col:
				return dist
			for i in range(8):
				nr = row + roww[i]
				nc = col + coll[i]
				if nr >= 0 and nc >= 0 and (nr < N) and (nc < N) and (vis[nr][nc] == 0):
					vis[nr][nc] = 1
					queue.append((nr, nc, dist + 1))
		return 0


class Solution:

	def isValid(self, row, col, n):
		if row >= 0 and row < n and (col >= 0) and (col < n):
			return True
		return False

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		count = 0
		dx = [1, 2, -1, 2, 1, -2, -1, -2]
		dy = [2, 1, -2, -1, -2, 1, 2, -1]
		queue = []
		queue.append([KnightPos[0] - 1, KnightPos[1] - 1, count])
		visited = [[False for i in range(N)] for j in range(N)]
		visited[KnightPos[0] - 1][KnightPos[1] - 1] = True
		while len(queue):
			t = queue[0]
			queue.pop(0)
			if t[0] == TargetPos[0] - 1 and t[1] == TargetPos[1] - 1:
				return t[2]
			for i in range(8):
				x = t[0] + dx[i]
				y = t[1] + dy[i]
				if self.isValid(x, y, N) and (not visited[x][y]):
					visited[x][y] = True
					queue.append([x, y, t[2] + 1])


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		if KnightPos == TargetPos:
			return 0
		distance = []
		for i in range(N):
			arr = []
			for j in range(N):
				arr.append(0)
			distance.append(arr)
		q = [(KnightPos[0] - 1, KnightPos[1] - 1)]
		visited = set()
		moves = [(2, 1), (-2, 1), (2, -1), (-2, -1), (-1, 2), (1, 2), (-1, -2), (1, -2)]
		steps = 0
		while q:
			pos = q.pop(0)
			visited.add(pos)
			for move in moves:
				x = pos[0] + move[0]
				y = pos[1] + move[1]
				if 0 <= x < N and 0 <= y < N and ((x, y) not in visited):
					visited.add((x, y))
					q.append((x, y))
					distance[x][y] = distance[pos[0]][pos[1]] + 1
					if x == TargetPos[0] - 1 and y == TargetPos[1] - 1:
						return distance[x][y]
		return -1


import queue

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		minimum_steps = -1
		visited = set((KnightPos[0], KnightPos[1]))
		moves = [(-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1)]
		source = (KnightPos[0], KnightPos[1], 0)
		q = queue.Queue()
		q.put(source)
		while not q.empty():
			(j, i, step) = q.get()
			if [j, i] == TargetPos:
				return step if minimum_steps == -1 else min(minimum_steps, step)
			for move in moves:
				column = j + move[0]
				row = i + move[1]
				if 1 <= row and row <= N and (1 <= column) and (column <= N):
					if (column, row) not in visited:
						visited.add((column, row))
						q.put((column, row, step + 1))
		return minimum_steps


class Solution:

	def minStepToReachTarget(self, KnightPos, targetPos, N):
		q = []
		KnightPos[0] -= 1
		KnightPos[1] -= 1
		targetPos[0] -= 1
		targetPos[1] -= 1
		steps = 0
		dr = [1, 1, -1, -1, -2, -2, 2, 2]
		dc = [2, -2, 2, -2, 1, -1, 1, -1]
		q.append([0, KnightPos])
		vis = [[0] * N for i in range(N)]
		if KnightPos[0] == targetPos[0] and KnightPos[1] == targetPos[1]:
			return 0
		while q:
			node = q.pop(0)
			steps = node[0]
			r = node[1][0]
			c = node[1][1]
			for i in range(len(dr)):
				nr = r + dr[i]
				nc = c + dc[i]
				if (nr >= 0 and nr < N) and (nc >= 0 and nc < N) and (vis[nr][nc] == 0):
					if nr == targetPos[0] and nc == targetPos[1]:
						return steps + 1
					q.append([steps + 1, [nr, nc]])
					vis[nr][nc] = 1
		return -1


from collections import deque

class Solution:

	def minStepToReachTarget(self, s, d, n):
		q = deque([(s[0], s[1], 0)])
		neigh = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]
		seen = set()
		seen.add((s[0], s[1]))
		while q:
			(i, j, steps) = q.popleft()
			if i == d[0] and j == d[1]:
				return steps
			for (x, y) in neigh:
				nx = i + x
				ny = j + y
				if 0 < nx <= n and 0 < ny <= n and ((nx, ny) not in seen):
					seen.add((nx, ny))
					q.append((nx, ny, steps + 1))
		return -1


import sys

class Solution:

	def isValid(self, i, j):
		if i > N or j > N or i <= 0 or (j <= 0):
			return False
		return True

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		dp = [[-1] * (N + 1) for i in range(N + 1)]
		dp[TargetPos[0]][TargetPos[1]] = 0
		q = []
		q.append((TargetPos[0], TargetPos[1]))
		while len(q) > 0:
			(i, j) = q.pop(0)
			x = [2, 2, -2, -2, 1, 1, -1, -1]
			y = [1, -1, 1, -1, 2, -2, 2, -2]
			for k in range(8):
				(ii, jj) = (i + x[k], j + y[k])
				if self.isValid(ii, jj) and dp[ii][jj] == -1:
					dp[ii][jj] = 1 + dp[i][j]
					q.append((ii, jj))
		return dp[KnightPos[0]][KnightPos[1]]


class Solution:

	def valid(self, i, j, n):
		return i >= 0 and j >= 0 and (i < n) and (j < n)

	def minStepToReachTarget(self, k, t, N):
		x = [1, 1, -1, -1, 2, 2, -2, -2]
		y = [2, -2, 2, -2, 1, -1, 1, -1]
		minStep = [[10000001] * N for i in range(N)]
		queue = []
		minStep[k[0] - 1][k[1] - 1] = 0
		queue.append([k[0] - 1, k[1] - 1])
		while len(queue) > 0:
			front = queue.pop(0)
			for i in range(8):
				a = x[i] + front[0]
				b = y[i] + front[1]
				if self.valid(a, b, N) and minStep[a][b] > minStep[front[0]][front[1]] + 1:
					minStep[a][b] = minStep[front[0]][front[1]] + 1
					queue.append([a, b])
		return minStep[t[0] - 1][t[1] - 1] if minStep[t[0] - 1][t[1] - 1] != 10000001 else -1


from collections import deque

class Solution:

	def safe(self, row, col, n):
		return True if row >= 1 and row <= n and (col >= 1) and (col <= n) else False

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		if KnightPos[0] == TargetPos[0] and KnightPos[1] == TargetPos[1]:
			return 0
		grid = [[0 for i in range(N + 1)] for j in range(N + 1)]
		row_move = [-1, 1, -1, 1, 2, 2, -2, -2]
		col_move = [2, 2, -2, -2, -1, 1, -1, 1]
		queue = deque()
		queue.append([KnightPos[1], KnightPos[0]])
		grid[KnightPos[1]][KnightPos[0]] = 0
		while queue:
			cell = queue.popleft()
			for i in range(8):
				row = cell[0] + row_move[i]
				col = cell[1] + col_move[i]
				if self.safe(row, col, N):
					parent_distance = grid[cell[0]][cell[1]]
					if grid[row][col] == 0:
						grid[row][col] = 1 + parent_distance
						queue.append([row, col])
					else:
						grid[row][col] = min(grid[row][col], 1 + parent_distance)
		ans = grid[TargetPos[1]][TargetPos[0]]
		return ans if ans != 0 else -1


from collections import deque

def getOptions(row, col):
	return [[row - 1, col - 2], [row - 1, col + 2], [row + 1, col - 2], [row + 1, col + 2], [row - 2, col - 1], [row - 2, col - 1], [row - 2, col + 1], [row + 2, col - 1], [row + 2, col + 1]]

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		if KnightPos == TargetPos:
			return 0
		grid = [[False for _ in range(N)] for _ in range(N)]
		queue = deque([[KnightPos[0] - 1, KnightPos[1] - 1, 0]])
		grid[KnightPos[0] - 1][KnightPos[1] - 1] = True
		while queue:
			(row, col, move) = queue.popleft()
			for (r, c) in getOptions(row, col):
				if r >= 0 and c >= 0 and (r < N) and (c < N) and (grid[r][c] == False):
					if r == TargetPos[0] - 1 and c == TargetPos[1] - 1:
						return move + 1
					grid[r][c] = True
					queue.append([r, c, move + 1])
		return -1


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		queue = [([KnightPos[0] - 1, KnightPos[1] - 1], 0)]
		visited = [[-1 for _ in range(N)] for _ in range(N)]
		while queue:
			l = len(queue)
			x = queue.pop(0)
			a1 = x[0][0]
			a2 = x[0][1]
			a3 = x[1]
			if a1 == TargetPos[0] - 1 and a2 == TargetPos[1] - 1:
				return a3
			if a1 + 1 < N and a2 + 2 < N and (visited[a1 + 1][a2 + 2] == -1):
				queue.append(([a1 + 1, a2 + 2], a3 + 1))
				visited[a1 + 1][a2 + 2] = 1
			if a1 - 1 >= 0 and a2 + 1 < N and (visited[a1 - 1][a2 + 1] == -1):
				queue.append(([a1 - 1, a2 + 2], a3 + 1))
				visited[a1 - 1][a2 + 1] = 1
			if a1 + 2 < N and a2 + 1 < N and (visited[a1 + 2][a2 + 1] == -1):
				queue.append(([a1 + 2, a2 + 1], a3 + 1))
				visited[a1 + 2][a2 + 1] = 1
			if a1 - 2 >= 0 and a2 + 1 < N and (visited[a1 - 2][a2 + 1] == -1):
				queue.append(([a1 - 2, a2 + 1], a3 + 1))
				visited[a1 - 2][a2 + 1] = 1
			if a1 + 1 < N and a2 - 2 >= 0 and (visited[a1 + 1][a2 - 2] == -1):
				queue.append(([a1 + 1, a2 - 2], a3 + 1))
				visited[a1 + 1][a2 - 2] = 1
			if a1 - 1 >= 0 and a2 - 2 >= 0 and (visited[a1 - 1][a2 - 2] == -1):
				queue.append(([a1 - 1, a2 - 2], a3 + 1))
				visited[a1 - 1][a2 - 2] = 1
			if a1 + 2 < N and a2 - 1 >= 0 and (visited[a1 + 2][a2 - 1] == -1):
				queue.append(([a1 + 2, a2 - 1], a3 + 1))
				visited[a1 + 2][a2 - 1] = 1
			if a1 - 2 >= 0 and a2 - 1 >= 0 and (visited[a1 - 2][a2 - 1] == -1):
				queue.append(([a1 - 2, a2 - 1], a3 + 1))
				visited[a1 - 2][a2 - 1] = 1


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		row = [-2, -2, -1, +1, +2, +2, -1, +1]
		col = [+1, -1, +2, +2, +1, -1, -2, -2]
		Ans = [9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999]
		visited = {(KnightPos[0], KnightPos[1]): 1}
		queue = [[KnightPos[0], KnightPos[1], 0]]

		def checkBoundries(r, c):
			if r < 1 or r > N or c < 1 or (c > N):
				return False
			return True

		def helper(x, y, count):
			if x == TargetPos[0] and y == TargetPos[1]:
				Ans[0] = min(Ans[0], count)
				return
			visited[x, y] = 1
			for i in range(8):
				r = x + row[i]
				c = y + col[i]
				if checkBoundries(r, c) and (r, c) not in visited:
					visited[r, c] = 1
					queue.append([r, c, count + 1])
		while len(queue) > 0:
			box = queue[0]
			queue.pop(0)
			helper(box[0], box[1], box[2])
		return Ans[0]


from queue import Queue

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		dx = [1, 1, -1, -1, 2, 2, -2, -2]
		dy = [-2, 2, -2, 2, -1, 1, -1, 1]

		def Adj(x, y):
			l = []
			for k in range(8):
				if x + dx[k] >= 1 and y + dy[k] >= 1 and (y + dy[k] <= N) and (x + dx[k] <= N):
					l.append((x + dx[k], y + dy[k]))
			return l
		q = Queue()
		level = {}
		vis = {}
		for i in range(1, N + 1):
			for j in range(1, N + 1):
				vis[i, j] = False
				level[i, j] = -1
		s = (KnightPos[0], KnightPos[1])
		q.put(s)
		vis[s] = True
		level[s] = 0
		while not q.empty():
			u = q.get()
			x = u[0]
			y = u[1]
			if x == TargetPos[0] and y == TargetPos[1]:
				return level[TargetPos[0], TargetPos[1]]
			a = Adj(x, y)
			for v in a:
				if not vis[v]:
					vis[v] = True
					level[v] = level[u] + 1
					q.put(v)
		return level[TargetPos[0], TargetPos[1]]


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		visited = [[False for i in range(N + 1)] for j in range(N + 1)]
		q = deque()
		q.append([KnightPos[0], KnightPos[1], 0])
		visited[KnightPos[0]][KnightPos[1]] = True
		di = [-2, -2, 2, 2, -1, 1, -1, 1]
		dj = [-1, 1, -1, 1, -2, -2, 2, 2]
		while q:
			(i, j, d) = q.popleft()
			if i == TargetPos[0] and j == TargetPos[1]:
				return d
			for idx in range(8):
				dii = di[idx]
				djj = dj[idx]
				if 1 <= i + dii <= N and 1 <= j + djj <= N and (not visited[i + dii][j + djj]):
					visited[i + dii][j + djj] = True
					q.append([i + dii, j + djj, d + 1])
		return -1


from collections import deque

class Solution:

	def isValid(self, x, y, N):
		return x >= 0 and x < N and (y >= 0) and (y < N)

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		dxy = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [1, -2], [-1, 2], [-1, -2]]
		KnightPos[0] -= 1
		KnightPos[1] -= 1
		TargetPos[0] -= 1
		TargetPos[1] -= 1
		vis = [[False for i in range(N)] for j in range(N)]
		q = deque()
		q.append([KnightPos[0], KnightPos[1], 0])
		vis[KnightPos[0]][KnightPos[1]] = True
		while len(q):
			cur = q.popleft()
			x = cur[0]
			y = cur[1]
			steps = cur[2]
			if x == TargetPos[0] and y == TargetPos[1]:
				return steps
			for i in range(8):
				n_x = x + dxy[i][0]
				n_y = y + dxy[i][1]
				if self.isValid(n_x, n_y, N) and vis[n_x][n_y] == False:
					q.append([n_x, n_y, steps + 1])
					vis[n_x][n_y] = True
		return -1


class Solution:

	def minStepToReachTarget(self, kp, tp, N):
		if kp == tp:
			return 0
		g = [[-1 for i in range(N)] for j in range(N)]
		g[tp[0] - 1][tp[1] - 1] = 0

		def check(a, b, n):
			return a >= 0 and a < n and (b >= 0) and (b < n)
		moves = [[1, 2], [-1, 2], [1, -2], [-1, -2], [2, 1], [-2, 1], [2, -1], [-2, -1]]
		q = [[tp[0] - 1, tp[1] - 1]]
		prev = 0
		while q:
			node = q.pop(0)
			prev = g[node[0]][node[1]]
			prev += 1
			for move in moves:
				(a, b) = (node[0] + move[0], node[1] + move[1])
				if check(a, b, N) and g[a][b] < 0:
					if [a + 1, b + 1] == kp:
						return prev
					g[a][b] = prev
					q.append([a, b])
		return -1


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		(start_row, start_col) = (KnightPos[0] - 1, KnightPos[1] - 1)
		(target_row, target_col) = (TargetPos[0] - 1, TargetPos[1] - 1)
		visited = [[False for _ in range(N)] for _ in range(N)]
		visited[start_row][start_col] = True
		queue = [(start_row, start_col, 0)]
		while queue:
			(row, col, dist) = queue.pop(0)
			if row == target_row and col == target_col:
				return dist
			moves = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]
			for move in moves:
				(new_row, new_col) = (row + move[0], col + move[1])
				if 0 <= new_row < N and 0 <= new_col < N and (not visited[new_row][new_col]):
					visited[new_row][new_col] = True
					queue.append((new_row, new_col, dist + 1))
		return 0


def isSafe(a, b, N):
	if a >= 0 and a < N and (b >= 0) and (b < N):
		return True
	return False

def dfs(sx, sy, visit, N, ex, ey, p):
	global steps
	if sx == ex and sy == ey:
		print(p)
		steps = min(steps, p)
		return
	visit[sx][sy] = 1
	x = [2, 2, 1, -1, -2, -2, -1, 1]
	y = [1, -1, 2, 2, 1, -1, -2, -2]
	for i in range(8):
		a = sx + x[i]
		b = sy + y[i]
		if isSafe(a, b, N) and visit[a][b] == 0:
			dfs(a, b, visit, N, ex, ey, p + 1)

def bfs(sx, sy, visit, N, ex, ey, p):
	global steps
	if sx == ex and sy == ey:
		steps = 0
		return
	q = [[sx, sy, p]]
	visit[sx][sy] = 1
	x = [2, 2, 1, -1, -2, -2, -1, 1]
	y = [1, -1, 2, 2, 1, -1, -2, -2]
	while len(q) > 0:
		[tx, ty, tp] = q.pop(0)
		if tx == ex and ty == ey:
			steps = tp
			return
		for i in range(8):
			a = tx + x[i]
			b = ty + y[i]
			if isSafe(a, b, N) and visit[a][b] == 0:
				q.append([a, b, tp + 1])
				visit[a][b] = 1

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		global steps
		steps = 100000000
		visit = [[0 for i in range(N)] for i in range(N)]
		bfs(KnightPos[0] - 1, KnightPos[1] - 1, visit, N, TargetPos[0] - 1, TargetPos[1] - 1, 0)
		return steps


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, n):
		q = []
		q.append([0, [KnightPos[0], KnightPos[1]]])
		visited = [[0 for i in range(n + 1)] for j in range(n + 1)]
		visited[KnightPos[0]][KnightPos[1]] = 1
		delr = [-2, -1, 1, 2, -2, -1, 1, 2]
		delc = [-1, -2, -2, -1, 1, 2, 2, 1]
		while len(q) != 0:
			(steps, cell) = q.pop(0)
			(row, col) = cell
			if row == TargetPos[0] and col == TargetPos[1]:
				return steps
			for k in range(8):
				nrow = row + delr[k]
				ncol = col + delc[k]
				if 1 <= nrow <= n and 1 <= ncol <= n and (visited[nrow][ncol] == 0):
					visited[nrow][ncol] = 1
					q.append([steps + 1, [nrow, ncol]])
		return -1


class Solution:

	def minStepToReachTarget(self, k, t, N):
		x = [2, 2, 1, -1, -2, -2, 1, -1]
		y = [-1, 1, 2, 2, -1, 1, -2, -2]
		if k[0] == t[0] and k[1] == t[1]:
			return 0
		vis = [[False for i in range(N + 1)] for j in range(N + 1)]
		q = []
		q.append((k[0], k[1]))
		count = 0
		while q:
			sz = len(q)
			count += 1
			for i in range(sz):
				temp = q.pop(0)
				(dx, dy) = (temp[0], temp[1])
				for d in range(8):
					(ni, nj) = (dx + x[d], dy + y[d])
					if ni > 0 and nj > 0 and (ni <= N) and (nj <= N) and (not vis[ni][nj]):
						if ni == t[0] and nj == t[1]:
							return count
						q.append((ni, nj))
						vis[ni][nj] = 1
		return -1


class Solution:

	def minStepToReachTarget(self, knightPos, t, N):
		q = [[knightPos[1] - 1, knightPos[0] - 1]]
		dist = [[float('inf') for i in range(N)] for i in range(N)]
		dist[knightPos[1] - 1][knightPos[0] - 1] = 0
		while q:
			(x, y) = q.pop(0)
			for (i, j) in ((x + 2, y + 1), (x + 2, y - 1), (x - 2, y + 1), (x - 2, y - 1), (x + 1, y - 2), (x - 1, y - 2), (x + 1, y + 2), (x - 1, y + 2)):
				if 0 <= i < N and 0 <= j < N:
					if dist[i][j] > dist[x][y] + 1:
						dist[i][j] = dist[x][y] + 1
						q.append([i, j])
		return dist[t[1] - 1][t[0] - 1]


class Solution:

	def is_valid(self, i, j, n, visited):
		if i >= 0 and i < n and (j >= 0) and (j < n) and (visited[i][j] == 'false'):
			return True
		return False

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		n = N
		tx = TargetPos[0] - 1
		ty = TargetPos[1] - 1
		x1 = KnightPos[0] - 1
		y1 = KnightPos[1] - 1
		if x1 == tx and y1 == ty:
			return 0
		visited = [['false'] * n for i in range(n)]
		q = []
		q.append([x1, y1])
		visited[x1][y1] = 'true'
		ans = 0
		while q:
			size = len(q)
			ans += 1
			while size != 0:
				(xx, yy) = q.pop(0)
				ax = [1, 1, -1, -1, 2, -2, 2, -2]
				ay = [2, -2, 2, -2, 1, 1, -1, -1]
				for i in range(8):
					nx = xx + ax[i]
					ny = yy + ay[i]
					if nx == tx and ny == ty:
						return ans
					if self.is_valid(nx, ny, n, visited):
						visited[nx][ny] = 'true'
						q.append([nx, ny])
				size -= 1
		return ans


from collections import deque

class Solution:

	def isValid(self, row, col, n):
		if row <= n and row > 0 and (col <= n) and (col > 0):
			return True
		return False

	def minStepToReachTarget(self, KnightPos, TargetPos, n):
		visited = [[0 for i in range(n + 1)] for j in range(n + 1)]
		q = deque()
		q.append([0, [KnightPos[0], KnightPos[1]]])
		visited[KnightPos[0]][KnightPos[1]] = 1
		kr = [-2, -2, -1, -1, 2, 2, 1, 1]
		kc = [-1, 1, -2, 2, -1, 1, -2, 2]
		while q:
			top = q.popleft()
			steps = top[0]
			row = top[1][0]
			col = top[1][1]
			if row == TargetPos[0] and col == TargetPos[1]:
				return steps
			for i in range(8):
				jrow = row + kr[i]
				jcol = col + kc[i]
				if self.isValid(jrow, jcol, n) and visited[jrow][jcol] == 0:
					q.append([steps + 1, [jrow, jcol]])
					visited[jrow][jcol] = 1
		return -1


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		(i, j) = KnightPos
		i -= 1
		j -= 1
		(x, y) = TargetPos
		x -= 1
		y -= 1
		visited = set()
		visited.add((i, j))
		q = deque()
		q.append([i, j, 0])
		while q:
			(r, c, d) = q.popleft()
			if r == x and c == y:
				return d
			for (dx, dy) in [[1, 2], [2, 1], [1, -2], [2, -1], [-1, -2], [-2, -1], [-2, 1], [-1, 2]]:
				nr = r + dx
				nc = c + dy
				if 0 <= nr < N and 0 <= nc < N and ((nr, nc) not in visited):
					visited.add((nr, nc))
					q.append([nr, nc, d + 1])
		return -1


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		q = [KnightPos]
		visited = [[-1] * (N + 1) for i in range(N + 1)]
		visited[KnightPos[0]][KnightPos[1]] = 0
		while q:
			current = q.pop(0)
			(row, col) = current
			cells = [(row - 1, col - 2), (row - 1, col + 2), (row - 2, col - 1), (row - 2, col + 1), (row + 1, col - 2), (row + 1, col + 2), (row + 2, col - 1), (row + 2, col + 1)]
			for (nrow, ncol) in cells:
				if 1 <= nrow < N + 1 and 1 <= ncol < N + 1 and (visited[nrow][ncol] == -1):
					visited[nrow][ncol] = visited[row][col] + 1
					q.append((nrow, ncol))
		return visited[TargetPos[0]][TargetPos[1]]


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		KnightPos[0] -= 1
		KnightPos[1] -= 1
		TargetPos[0] -= 1
		TargetPos[1] -= 1
		board = [[0] * N for _ in range(N)]
		queue = deque()
		queue.append(KnightPos + [0])
		while queue:
			(i, j, count) = queue.popleft()
			if board[i][j]:
				continue
			board[i][j] = 1
			if [i, j] == TargetPos:
				return count
			if i > 1 and j > 0:
				queue.append((i - 2, j - 1, count + 1))
			if i > 1 and j < N - 1:
				queue.append((i - 2, j + 1, count + 1))
			if i > 0 and j > 1:
				queue.append((i - 1, j - 2, count + 1))
			if i > 0 and j < N - 2:
				queue.append((i - 1, j + 2, count + 1))
			if i < N - 1 and j > 1:
				queue.append((i + 1, j - 2, count + 1))
			if i < N - 1 and j < N - 2:
				queue.append((i + 1, j + 2, count + 1))
			if i < N - 2 and j > 0:
				queue.append((i + 2, j - 1, count + 1))
			if i < N - 2 and j < N - 1:
				queue.append((i + 2, j + 1, count + 1))
		return -1


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		(ix, iy) = KnightPos
		ix -= 1
		iy -= 1
		(tx, ty) = TargetPos
		tx -= 1
		ty -= 1
		visited = set()
		x = deque()
		x.append((ix, iy))
		visited.add((ix, iy))
		steps = 0
		while x:
			for _ in range(len(x)):
				(i, j) = x.popleft()
				if i == tx and j == ty:
					return steps
				for (dx, dy) in [[1, 2], [2, 1], [1, -2], [2, -1], [-1, -2], [-2, -1], [-2, 1], [-1, 2]]:
					newi = i + dx
					newj = j + dy
					if 0 <= newi < N and 0 <= newj < N and ((newi, newj) not in visited):
						visited.add((newi, newj))
						x.append((newi, newj))
			steps += 1
		return -1


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		if KnightPos == TargetPos:
			return 0
		dp = [[0] * N for _ in range(N)]
		q = []
		q.append([KnightPos[0] - 1, KnightPos[1] - 1])
		dp[KnightPos[0] - 1][KnightPos[1] - 1] = 0
		x = [2, 1, -1, -2, -2, -1, 1, 2]
		y = [1, 2, 2, 1, -1, -2, -2, -1]

		def Valid(i, j):
			if i < 0 or j < 0 or i > N - 1 or (j > N - 1) or (dp[i][j] != 0):
				return False
			return True
		while len(q) != 0:
			(i, j) = q.pop(0)
			for k in range(8):
				if Valid(i + x[k], j + y[k]):
					dp[i + x[k]][j + y[k]] = dp[i][j] + 1
					if i + x[k] == TargetPos[0] - 1 and j + y[k] == TargetPos[1] - 1:
						return dp[i + x[k]][j + y[k]]
					q.append([i + x[k], j + y[k]])


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):

		def valid_next(i, j, N):
			directions = [[-1, -2], [-2, -1], [-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2]]
			ret = []
			for d in directions:
				x = i + d[0]
				y = j + d[1]
				if x > 0 and y > 0 and (x <= N) and (y <= N):
					ret.append([x, y])
			return ret
		que = deque()
		depth = 0
		que.append(KnightPos)
		visited = [[False] * (N + 1) for _ in range(N + 1)]
		visited[KnightPos[0]][KnightPos[1]] = True
		while que:
			n = len(que)
			while n > 0:
				cur_pos = que.popleft()
				if cur_pos[0] == TargetPos[0] and cur_pos[1] == TargetPos[1]:
					return depth
				all_next = valid_next(cur_pos[0], cur_pos[1], N)
				for nxt in all_next:
					if not visited[nxt[0]][nxt[1]]:
						que.append(nxt)
						visited[nxt[0]][nxt[1]] = True
				n -= 1
			depth += 1
		return -1 if len(que) == 0 else depth


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		delrow = [1, 2, -2, -1, -1, -2, 1, 2]
		delcol = [2, 1, 1, 2, -2, -1, -2, -1]
		queue = [[KnightPos[0], KnightPos[1], 0]]
		visited = [[0 for i in range(N + 1)] for j in range(N + 1)]
		visited[KnightPos[0]][KnightPos[1]] = 1
		while queue:
			r = queue[0][0]
			c = queue[0][1]
			steps = queue[0][2]
			queue.pop(0)
			if r == TargetPos[0] and c == TargetPos[1]:
				return steps
			for i in range(8):
				nr = r + delrow[i]
				nc = c + delcol[i]
				if nr >= 0 and nr < N + 1 and (nc >= 0) and (nc < N + 1) and (not visited[nr][nc]):
					visited[nr][nc] = 1
					queue.append([nr, nc, steps + 1])


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		R3 = [[0, 3, 2, 3], [3, 2, 1, 2], [2, 1, 4, 3], [3, 2, 3, 2]]
		x = abs(TargetPos[0] - KnightPos[0])
		y = abs(TargetPos[1] - KnightPos[1])
		a = 1
		b = 2
		result = 0
		while x > 3 or y > 3:
			if x > y:
				if x % 2 == 0 and x - y > 1:
					a = 2
					b = 1
				else:
					a = 1
					b = 2
			elif y % 2 == 0 and y - x > 1:
				a = 1
				b = 2
			else:
				a = 2
				b = 1
			x = abs(x - a)
			y = abs(y - b)
			result += 1
			if x < 4 and y < 4:
				return result + R3[x][y]
		return R3[x][y]


from heapq import heappush, heappop

class Solution:

	def bfs(self, node, pq, distance, row_poss, col_poss, n, target):
		while len(pq):
			(steps, node) = pq[0]
			if node[0] == target[0] and node[1] == target[1]:
				return steps
			heappop(pq)
			for k in range(8):
				row = node[0] + row_poss[k]
				col = node[1] + col_poss[k]
				if row >= 1 and row <= n and (col >= 1) and (col <= n):
					if distance[node[0]][node[1]] + 1 < distance[row][col]:
						distance[row][col] = distance[node[0]][node[1]] + 1
						heappush(pq, (distance[row][col], (row, col)))
		return -1

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		pq = []
		distance = [[float('inf') for x in range(N + 1)] for x in range(N + 1)]
		row_poss = [-2, -2, -1, -1, 1, 1, 2, 2]
		col_poss = [1, -1, 2, -2, 2, -2, 1, -1]
		distance[KnightPos[0]][KnightPos[1]] = 0
		heappush(pq, (0, (KnightPos[0], KnightPos[1])))
		return self.bfs((KnightPos[0], KnightPos[1]), pq, distance, row_poss, col_poss, N, TargetPos)


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		kx = KnightPos[0] - 1
		ky = KnightPos[1] - 1
		tx = TargetPos[0] - 1
		ty = TargetPos[1] - 1
		if kx == tx and ky == ty:
			return 0
		A = [[False for i in range(N + 1)] for j in range(N + 1)]
		cl = [-2, -1, +1, +2, -2, -1, +1, +2]
		rl = [-1, -2, -2, -1, +1, +2, +2, +1]
		A[ky][kx] = 0
		q = deque()
		q.append([ky, kx])
		while len(q) > 0:
			temp = q.popleft()
			row = temp[0]
			col = temp[1]
			for i in range(8):
				newrow = row + rl[i]
				newcol = col + cl[i]
				if newrow >= 0 and newrow < N and (newcol >= 0) and (newcol < N):
					if A[newrow][newcol] == False and newrow == ty and (newcol == tx):
						return A[row][col] + 1
					elif A[newrow][newcol] == False:
						q.append([newrow, newcol])
						A[newrow][newcol] = A[row][col] + 1
		return -1


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		KnightPos = [KnightPos[0] - 1, KnightPos[1] - 1]
		TargetPos = [TargetPos[0] - 1, TargetPos[1] - 1]
		q = []
		q.append(KnightPos)
		dirr = [[1, 2], [2, 1], [1, -2], [2, -1], [-1, -2], [-2, -1], [-1, 2], [-2, 1]]
		dis = [[10 ** 8 for _ in range(N)] for _ in range(N)]
		dis[KnightPos[0]][KnightPos[1]] = 0
		while q:
			temp = q.pop(0)
			for (i, j) in dirr:
				newr = temp[0] + i
				newc = temp[1] + j
				if newr < 0 or newc < 0 or newr >= N or (newc >= N) or (dis[newr][newc] <= dis[temp[0]][temp[1]] + 1):
					continue
				q.append([newr, newc])
				dis[newr][newc] = dis[temp[0]][temp[1]] + 1
		if dis[TargetPos[0]][TargetPos[1]] == 10 ** 8:
			return -1
		return dis[TargetPos[0]][TargetPos[1]]


import sys

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		x_move = [1, 1, -1, -1, 2, 2, -2, -2]
		y_move = [2, -2, 2, -2, -1, 1, -1, 1]
		queue = []
		visited = [[False for _ in range(N + 1)] for _ in range(N + 1)]
		queue.append([KnightPos[0], KnightPos[1], 0])
		visited[KnightPos[0]][KnightPos[1]] = True
		min_step_count = sys.maxsize
		(target_x, target_y) = (TargetPos[0], TargetPos[1])
		while len(queue) != 0:
			top = queue.pop(0)
			(X, Y, step_count) = (top[0], top[1], top[2])
			if [X, Y] == [target_x, target_y]:
				min_step_count = min(min_step_count, step_count)
			else:
				for (x, y) in zip(x_move, y_move):
					(X_new, Y_new) = (X + x, Y + y)
					if self.isValidPosition(X_new, Y_new, N) and (not visited[X_new][Y_new]):
						queue.append([X_new, Y_new, step_count + 1])
						visited[X_new][Y_new] = True
		return min_step_count

	def isValidPosition(self, X, Y, N):
		return 1 <= X <= N and 1 <= Y <= N


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		visited = [[False for j in range(N + 1)] for i in range(N + 1)]
		x1 = KnightPos[0]
		y1 = KnightPos[1]
		x2 = TargetPos[0]
		y2 = TargetPos[1]
		dire = [(2, 1), (2, -1), (1, 2), (1, -2), (-2, 1), (-2, -1), (-1, 2), (-1, -2)]
		visited[x1][y1] = True
		q = [(x1, y1, 0)]
		while q:
			(i, j, dist) = q.pop(0)
			if i == x2 and j == y2:
				return dist
			for (dx, dy) in dire:
				newR = i + dx
				newC = j + dy
				if newR >= 1 and newR <= N and (newC >= 1) and (newC <= N) and (not visited[newR][newC]):
					visited[newR][newC] = True
					q.append((newR, newC, dist + 1))


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		board = [[0 for j in range(N)] for i in range(N)]
		x1 = KnightPos[0]
		y1 = KnightPos[1]
		x2 = TargetPos[0]
		y2 = TargetPos[1]
		q = [(x1 - 1, y1 - 1)]
		while q:
			(i, j) = q.pop(0)
			if i + 1 >= 0 and i + 1 < N and (j + 2 >= 0) and (j + 2 < N) and (board[i + 1][j + 2] == 0):
				board[i + 1][j + 2] += board[i][j] + 1
				q.append((i + 1, j + 2))
			if i - 1 >= 0 and i - 1 < N and (j + 2 >= 0) and (j + 2 < N) and (board[i - 1][j + 2] == 0):
				board[i - 1][j + 2] += board[i][j] + 1
				q.append((i - 1, j + 2))
			if i - 2 >= 0 and i - 2 < N and (j + 1 >= 0) and (j + 1 < N) and (board[i - 2][j + 1] == 0):
				board[i - 2][j + 1] += board[i][j] + 1
				q.append((i - 2, j + 1))
			if i + 2 >= 0 and i + 2 < N and (j + 1 >= 0) and (j + 1 < N) and (board[i + 2][j + 1] == 0):
				board[i + 2][j + 1] += board[i][j] + 1
				q.append((i + 2, j + 1))
			if i - 1 >= 0 and i - 1 < N and (j - 2 >= 0) and (j - 2 < N) and (board[i - 1][j - 2] == 0):
				board[i - 1][j - 2] += board[i][j] + 1
				q.append((i - 1, j - 2))
			if i + 1 >= 0 and i + 1 < N and (j - 2 >= 0) and (j - 2 < N) and (board[i + 1][j - 2] == 0):
				board[i + 1][j - 2] += board[i][j] + 1
				q.append((i + 1, j - 2))
			if i - 2 >= 0 and i - 2 < N and (j - 1 >= 0) and (j - 1 < N) and (board[i - 2][j - 1] == 0):
				board[i - 2][j - 1] += board[i][j] + 1
				q.append((i - 2, j - 1))
			if i + 2 >= 0 and i + 2 < N and (j - 1 >= 0) and (j - 1 < N) and (board[i + 2][j - 1] == 0):
				board[i + 2][j - 1] += board[i][j] + 1
				q.append((i + 2, j - 1))
		return board[x2 - 1][y2 - 1]


from queue import Queue

def bfs(kp, tp, n):
	(nkp, ntp) = ((n - kp[1], kp[0] - 1), (n - tp[1], tp[0] - 1))
	stack = Queue()
	stack.put([nkp, 0])
	visited = set()
	while not stack.empty():
		pop = stack.get()
		(top, level) = (pop[0], pop[1])
		if top == ntp:
			return level
		for ngh in isValid(top[0], top[1], n):
			if ngh not in visited:
				visited.add(ngh)
				stack.put([ngh, level + 1])

def isValid(i, j, n):
	neighs = []
	for (a, b) in zip([-2, -2, -1, 1, 2, 2, 1, -1], [-1, 1, 2, 2, 1, -1, -2, -2]):
		(ta, tb) = (a + i, b + j)
		if ta >= 0 and ta < n and (tb >= 0) and (tb < n):
			neighs.append((ta, tb))
	return neighs

class Solution:

	def minStepToReachTarget(self, kp, tp, n):
		return bfs(kp, tp, n)


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		visited = [[0 for _ in range(N)] for _ in range(N)]
		visited[KnightPos[0] - 1][KnightPos[1] - 1] = 1
		validpos = [[2, -1], [2, 1], [1, -2], [1, 2], [-1, -2], [-1, 2], [-2, -1], [-2, 1]]
		q = [KnightPos, [-1]]
		ans = 10 ** 10
		level = 0
		while q:
			temp = q.pop(0)
			if temp[0] == -1:
				level += 1
				if q:
					q.append([-1])
			elif ans < level:
				break
			else:
				if temp == TargetPos and ans > level:
					ans = level
				for (x, y) in validpos:
					if 0 < temp[0] + x < N + 1 and 0 < temp[1] + y < N + 1 and (visited[temp[0] + x - 1][temp[1] + y - 1] == 0):
						visited[temp[0] + x - 1][temp[1] + y - 1] = 1
						q.append([temp[0] + x, temp[1] + y])
		if ans == 10 ** 10:
			return -1
		return ans


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		if KnightPos == TargetPos:
			return 0
		MAX = 1000000
		board = []
		for y in range(N):
			board.append([])
			for x in range(N):
				board[y].append(MAX)
		moves = []
		moves.append([1, 2])
		moves.append([-1, 2])
		moves.append([1, -2])
		moves.append([-1, -2])
		moves.append([2, 1])
		moves.append([-2, 1])
		moves.append([2, -1])
		moves.append([-2, -1])
		board[N - KnightPos[1]][KnightPos[0] - 1] = 0
		board[N - TargetPos[1]][TargetPos[0] - 1] = -1
		queue = [[N - KnightPos[1], KnightPos[0] - 1]]
		while len(queue) > 0:
			item = queue[0]
			del queue[0]
			y = item[0]
			x = item[1]
			if board[y][x] != MAX and board[y][x] != -1:
				for move in moves:
					_y = y + move[0]
					_x = x + move[1]
					if -1 < _y < N and -1 < _x < N:
						_new = board[y][x] + 1
						if board[_y][_x] == -1:
							return _new
						if board[_y][_x] <= _new:
							continue
						else:
							board[_y][_x] = _new
							queue.append([_y, _x])


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		visit = set()
		q = deque()
		i = KnightPos[0] - 1
		j = KnightPos[1] - 1
		fi = TargetPos[0] - 1
		fj = TargetPos[1] - 1
		if i == fi and j == fj:
			return 0
		q.append([i, j])
		visit.add((i, j))
		steps = 0
		directions = [[-2, -1], [-2, 1], [2, 1], [2, -1], [-1, -2], [-1, 2], [1, 2], [1, -2]]

		def isValid(i, j):
			if i < 0 or j < 0 or i == N or (j == N) or ((i, j) in visit):
				return False
			return True
		while q:
			l = len(q)
			for i in range(l):
				(ci, cj) = q.popleft()
				if ci == fi and cj == fj:
					return steps
				for (dr, dc) in directions:
					r = ci + dr
					c = cj + dc
					if r == fi and c == fj:
						return steps + 1
					if isValid(r, c):
						visit.add((r, c))
						q.append([r, c])
			steps += 1
		return -1


def isValid(i, j, n, vis):
	if i >= 0 and j >= 0 and (i < n) and (j < n) and (vis[i][j] == 0):
		return True
	return False

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, n):
		tx = TargetPos[0] - 1
		ty = TargetPos[1] - 1
		x1 = KnightPos[0] - 1
		y1 = KnightPos[1] - 1
		q = []
		if x1 == tx and y1 == ty:
			return 0
		q.append([x1, y1])
		vis = [[0 for i in range(n)] for j in range(n)]
		vis[x1][y1] = 1
		ans = 0
		while len(q) != 0:
			size = len(q)
			ans += 1
			while size != 0:
				ele = q.pop(0)
				xx = ele[0]
				yy = ele[1]
				ax = [1, 1, -1, -1, 2, -2, 2, -2]
				ay = [2, -2, 2, -2, 1, 1, -1, -1]
				for i in range(8):
					nx = xx + ax[i]
					ny = yy + ay[i]
					if nx == tx and ty == ny:
						return ans
					if isValid(nx, ny, n, vis):
						vis[nx][ny] = 1
						q.append([nx, ny])
				size -= 1
		return ans


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		(ik, jk) = KnightPos = tuple(KnightPos)
		TargetPos = tuple(TargetPos)
		dist = [[False for i in range(N + 1)] for j in range(N + 1)]
		dist[ik][jk] = 0
		p_q = [KnightPos]
		while len(p_q) > 0:
			(i, j) = point = p_q.pop(0)
			dist_i = dist[i][j]
			if TargetPos[0] == i and TargetPos[1] == j:
				return dist[i][j]
			self.add_next_valid_points(point, dist, p_q, N)
		return -1

	def add_next_valid_points(self, crnt_point, dist, p_q, N):
		(i, j) = crnt_point
		points = [(i + 2, j + 1), (i + 2, j - 1), (i - 2, j + 1), (i - 2, j - 1), (i + 1, j + 2), (i + 1, j - 2), (i - 1, j + 2), (i - 1, j - 2)]
		crnt_dist = dist[i][j]
		for point in points:
			(ip, jp) = point
			if self.is_valid_point(point, N) and (not dist[ip][jp]):
				p_q.append(point)
				dist[ip][jp] = crnt_dist + 1

	def is_valid_point(self, point, N):
		if point[0] < 1 or point[0] > N:
			return False
		if point[1] < 1 or point[1] > N:
			return False
		return True