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.If it cannot reach the target position return -1.
Note:
The initial and the target position co-ordinates of Knight have been given accoring 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). 
Example 2:
Input:
N=8
knightPos[ ] = {7, 7}
targetPos[ ] = {1, 5}
Output:
4
Explanation:
Knight takes 4 steps to reach from
(7, 7) to (1, 5):
(4, 5) -> (6, 5) -> (5, 3) -> (7, 2) -> (1, 5).
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function minStepToReachTarget() which takes the inital position of Knight (KnightPos), the target position of Knight (TargetPos) and the size of the chess board (N) as an input parameters and returns the minimum number of steps required by the knight to reach from its current position to the given target position.If it cannot reach the target position return -1.
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: Graph algorithms

Data structures

Graph traversal

Starter code: class Solution:

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

		#Code here

Solutions:
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 for i in range(N)] for j in range(N)]
		q = [[0, [KnightPos[0] - 1, KnightPos[1] - 1]]]
		vis[KnightPos[0] - 1][KnightPos[1] - 1] = 1
		r1 = [1, 1, -1, -1, 2, 2, -2, -2]
		c1 = [2, -2, 2, -2, 1, -1, 1, -1]
		while q:
			n = q.pop(0)
			cnt = n[0]
			r = n[1][0]
			c = n[1][1]
			if r == TargetPos[0] - 1 and c == TargetPos[1] - 1:
				return cnt
			for i in range(8):
				if r + r1[i] >= 0 and r + r1[i] < N and (c + c1[i] >= 0) and (c + c1[i] < N) and (vis[r + r1[i]][c + c1[i]] == 0):
					vis[r + r1[i]][c + c1[i]] = 1
					q.append([cnt + 1, [r + r1[i], c + c1[i]]])
		return -1


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		vis = set()
		q = [[0, [KnightPos[0] - 1, KnightPos[1] - 1]]]
		vis.add((KnightPos[0] - 1, KnightPos[1] - 1))
		r1 = [1, 1, -1, -1, 2, 2, -2, -2]
		c1 = [2, -2, 2, -2, 1, -1, 1, -1]
		ans = float('inf')
		while q:
			n = q.pop(0)
			cnt = n[0]
			r = n[1][0]
			c = n[1][1]
			if r == TargetPos[0] - 1 and c == TargetPos[1] - 1:
				return cnt
			for i in range(8):
				nr = r + r1[i]
				nc = c + c1[i]
				if nr >= 0 and nr < N and (nc >= 0) and (nc < N) and ((nr, nc) not in vis):
					vis.add((nr, nc))
					q.append([cnt + 1, [nr, nc]])
		return -1


class Solution:

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


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		marked = [[0 for i in range(N)] for j in range(N)]
		marked[KnightPos[0] - 1][KnightPos[1] - 1] = 1
		q = deque()
		q.append(KnightPos[0] - 1)
		q.append(KnightPos[1] - 1)
		q.append(0)
		dx = [-2, -2, -1, -1, 1, 1, 2, 2]
		dy = [-1, 1, -2, 2, -2, 2, -1, 1]
		while len(q) > 0:
			x = q.popleft()
			y = q.popleft()
			dist = q.popleft()
			if x == TargetPos[0] - 1 and y == TargetPos[1] - 1:
				return dist
			for i in range(8):
				nx = x + dx[i]
				ny = y + dy[i]
				if nx >= 0 and nx < N and (ny >= 0) and (ny < N) and (not marked[nx][ny]):
					q.append(nx)
					q.append(ny)
					q.append(dist + 1)
					marked[nx][ny] = 1
		return -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)
		if target[0] < 0 or target[0] >= n or target[1] < 0 or (target[1] >= n):
			return -1
		moves = [(2, 1), (1, 2), (-2, 1), (-1, 2), (2, -1), (1, -2), (-2, -1), (-1, -2)]
		visited = [[False for _ in range(n)] for _ in range(n)]
		dist = [[float('inf') for _ in range(n)] for _ in range(n)]
		queue = [(start[0], start[1], 0)]
		visited[start[0]][start[1]] = True
		dist[start[0]][start[1]] = 0
		while queue:
			(x, y, steps) = queue.pop(0)
			if x == target[0] and y == target[1]:
				return steps
			for (dx, dy) in moves:
				(nx, ny) = (x + dx, y + dy)
				if 0 <= nx < n and 0 <= ny < n and (not visited[nx][ny]):
					visited[nx][ny] = True
					dist[nx][ny] = steps + 1
					queue.append((nx, ny, steps + 1))
		return -1


class Solution:

	def minStepToReachTarget(self, knightPos, targetPos, N):
		tx = targetPos[0] - 1
		ty = targetPos[1] - 1
		xx = knightPos[0] - 1
		xy = knightPos[1] - 1
		if xx == tx and ty == xy:
			return 0
		Queue = []
		ans = 0
		visited = [[0 for i in range(N)] for j in range(N)]
		Queue.append([xx, xy])
		while len(Queue) != 0:
			L = len(Queue)
			ans += 1
			while L != 0:
				test = Queue.pop(0)
				testx = test[0]
				testy = test[1]
				X = [1, -1, 1, -1, 2, 2, -2, -2]
				Y = [2, 2, -2, -2, 1, -1, 1, -1]
				j = 0
				while j < 8:
					t1 = testx + X[j]
					t2 = testy + Y[j]
					if t1 == tx and t2 == ty:
						return ans
					if t1 >= 0 and t2 >= 0 and (t1 < N) and (t2 < N) and (visited[t1][t2] == 0):
						Queue.append([t1, t2])
						visited[t1][t2] = 1
					j += 1
				L -= 1
		return ans


from collections import deque

class Solution:

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

		def getNextMove(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)]
		que = deque([(KnightPos[0], KnightPos[1])])
		visited = set([(KnightPos[0], KnightPos[1])])
		step = 0
		while que:
			for _ in range(len(que)):
				(row, col) = que.popleft()
				if row == TargetPos[0] and col == TargetPos[1]:
					return step
				for (nextRow, nextCol) in getNextMove(row, col):
					if nextRow < 1 or nextRow > N or nextCol < 1 or (nextCol > N) or ((nextRow, nextCol) in visited):
						continue
					que.append((nextRow, nextCol))
					visited.add((nextRow, nextCol))
			step += 1
		return -1


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		m = N
		n = N
		vis = set()
		dictio = {(-2, -1), (-2, 1), (-1, -2), (-1, 2), (2, -1), (2, 1), (1, -2), (1, 2)}
		q = deque()
		(kR, kC) = KnightPos
		kR -= 1
		kC -= 1
		(tR, tC) = TargetPos
		tR -= 1
		tC -= 1
		q.appendleft((kR, kC, 0))
		vis.add((kR, kC))
		while q:
			(row, col, steps) = q.pop()
			if row == tR and col == tC:
				return steps
			for (di, dj) in dictio:
				(n_i, n_j) = (row + di, col + dj)
				if n_i >= 0 and n_i < m and (n_j >= 0) and (n_j < n) and ((n_i, n_j) not in vis):
					vis.add((n_i, n_j))
					q.appendleft((n_i, n_j, steps + 1))
		return -1


class Node:

	def __init__(self, row, col, step):
		self.row = row
		self.col = col
		self.step = step

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		dx = [2, 2, -2, -2, 1, 1, -1, -1]
		dy = [1, -1, 1, -1, 2, -2, 2, -2]
		start_pos = Node(KnightPos[0], KnightPos[1], 0)
		target_pos = Node(TargetPos[0], TargetPos[1], 0)
		visited = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
		visited[start_pos.row][start_pos.col] = 1
		queue = [start_pos]
		while len(queue):
			curr_pos = queue.pop(0)
			if curr_pos.row == target_pos.row and curr_pos.col == target_pos.col:
				return curr_pos.step
			for i in range(8):
				x = curr_pos.row + dx[i]
				y = curr_pos.col + dy[i]
				if x >= 1 and x <= N and (y >= 1) and (y <= N) and (visited[x][y] == 0):
					node = Node(x, y, curr_pos.step + 1)
					queue.append(node)
					visited[x][y] = 1
		return -1


from collections import deque

class Solution:

	def minStepToReachTarget(self, src, des, N):
		visited = [[0 for _ in range(N)] for _ in range(N)]
		queue = deque()
		(i, j) = src
		cnt = 0
		queue.append((cnt, i - 1, j - 1))
		visited[i - 1][j - 1] = 1
		while queue:
			(cnt, x, y) = 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((cnt + 1, new_x, new_y))
		return -1


from collections import deque

def isSafe(i, j, m, n):
	if i < 0 or j < 0 or i >= m or (j >= n):
		return False
	return True

class Solution:

	def minStepToReachTarget(self, initial, target, n):
		dx = [2, 2, -2, -2, 1, 1, -1, -1]
		dy = [1, -1, 1, -1, 2, -2, 2, -2]
		q = deque([])
		q.append([initial[0] - 1, initial[1] - 1, 0])
		vis = [[0 for j in range(n)] for i in range(n)]
		vis[initial[0] - 1][initial[1] - 1] = 1
		while q:
			(x, y, dist) = q.popleft()
			if x == target[0] - 1 and y == target[1] - 1:
				return dist
			for i in range(8):
				xx = x + dx[i]
				yy = y + dy[i]
				if isSafe(xx, yy, n, n) and vis[xx][yy] == 0:
					vis[xx][yy] = 1
					q.append([xx, yy, dist + 1])
		return -1


class Solution:

	def is_valid(self, newx, newy, visited, n):
		if newx < 0 or newx >= n or newy < 0 or (newy >= n) or ((newx, newy) in visited):
			return False
		return True

	def minStepToReachTarget(self, knight, target, n):
		kx = knight[0]
		ky = knight[1]
		tx = target[0]
		ty = target[1]
		if kx == tx and ky == ty:
			return 0
		steps = [(-2, -1), (-2, 1), (2, -1), (2, 1), (1, 2), (-1, 2), (1, -2), (-1, -2)]
		q = list()
		q.append((kx, ky))
		visited = set()
		visited.add((kx, ky))
		step = 0
		while len(q):
			size = len(q)
			while size:
				size -= 1
				(curx, cury) = q.pop(0)
				for i in steps:
					newx = curx + i[0]
					newy = cury + i[1]
					if newx == tx and newy == ty:
						return step + 1
					if self.is_valid(newx, newy, visited, n):
						visited.add((newx, newy))
						q.append((newx, newy))
			step += 1
		return step


import collections

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		di = [2, 1, -1, -2, -2, -1, 1, 2]
		dj = [1, 2, 2, 1, -1, -2, -2, -1]
		q = collections.deque([(KnightPos[0] - 1, KnightPos[1] - 1)])
		visited = set()
		visited.add((KnightPos[0] - 1, KnightPos[1] - 1))
		target = (TargetPos[0] - 1, TargetPos[1] - 1)
		steps = 0
		while q:
			for k in range(len(q)):
				(i, j) = q.popleft()
				if i == target[0] and j == target[1]:
					return steps
				for d in range(8):
					newi = i + di[d]
					newj = j + dj[d]
					if not (0 <= newi < N and 0 <= newj < N):
						continue
					if (newi, newj) in visited:
						continue
					q.append((newi, newj))
					visited.add((newi, newj))
			steps += 1
		return steps


from collections import deque

class Solution:

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

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


from collections import deque

class Solution:

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


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		KnightPos = (KnightPos[0] - 1, KnightPos[1] - 1)
		TargetPos = (TargetPos[0] - 1, TargetPos[1] - 1)
		if KnightPos[0] == TargetPos[0] and KnightPos[1] == TargetPos[1]:
			return 0
		moves = [(2, -1), (2, 1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]
		visited = [[False] * N for _ in range(N)]
		q = deque()
		q.append((KnightPos[0], KnightPos[1], 0))
		visited[KnightPos[0]][KnightPos[1]] = True
		while q:
			(x, y, dist) = q.popleft()
			for move in moves:
				(mx, my) = (x + move[0], y + move[1])
				if 0 <= mx < N and 0 <= my < N and (not visited[mx][my]):
					if mx == TargetPos[0] and my == TargetPos[1]:
						return dist + 1
					q.append((mx, my, dist + 1))
					visited[mx][my] = True
		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


from collections import deque

class Solution:

	def minStepToReachTarget(self, knightPos, targetPos, N):
		if knightPos == targetPos:
			return 0
		(r, c, queue, directions) = (N, N, deque([knightPos]), [(-1, 2), (1, 2), (-1, -2), (1, -2), (-2, 1), (2, 1), (-2, -1), (2, -1)])
		level = 0
		vis = [[0 for i in range(c + 1)] for j in range(r + 1)]
		vis[knightPos[0]][knightPos[-1]] = 1
		while queue:
			for _ in range(len(queue)):
				(x, y) = queue.popleft()
				for (i, j) in directions:
					(new_x, new_y) = (x + i, y + j)
					if new_x == targetPos[0] and new_y == targetPos[1]:
						return level + 1
					if new_x < 0 or new_y < 0 or new_x > r or (new_y > c) or (vis[new_x][new_y] == 1):
						continue
					vis[new_x][new_y] = 1
					queue.append([new_x, new_y])
			level += 1
		return -1


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


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		dr = [1, -1, 1, -1, 2, -2, 2, -2]
		dc = [2, 2, -2, -2, 1, 1, -1, -1]
		Q = deque([[KnightPos[0], KnightPos[1], 0]])
		visit = [[False for c in range(N)] for r in range(N)]
		while Q:
			(r, c, step) = Q.popleft()
			if r < 1 or r > N or c < 1 or (c > N) or visit[r - 1][c - 1]:
				continue
			if r == TargetPos[0] and c == TargetPos[1]:
				return step
			visit[r - 1][c - 1] = True
			for i in range(8):
				newR = r + dr[i]
				newC = c + dc[i]
				Q.append([newR, newC, step + 1])
		return -1


class Solution:

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


from collections import deque

def bfs(kp, tp, n):
	(nkp, ntp) = ((n - kp[1], kp[0] - 1), (n - tp[1], tp[0] - 1))
	stack = deque()
	stack.append([nkp, 0])
	visited = set()
	while stack:
		top = stack.popleft()
		(a, b) = (top[0], top[1])
		if a == ntp:
			return b
		for ngh in isValid(a[0], a[1], n):
			if ngh not in visited:
				stack.append([ngh, b + 1])
				visited.add(ngh)

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 isValid(self, i, j, n):
		return i > 0 and j > 0 and (i <= n) and (j <= n)

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		queue = [[KnightPos[0], KnightPos[1], 0]]
		seen = {(KnightPos[0], KnightPos[1]): True}
		direc = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [1, -2], [-1, -2], [-1, 2]]
		while len(queue):
			(x, y, d) = queue.pop(0)
			if x == TargetPos[0] and y == TargetPos[1]:
				return d
			for (i, j) in direc:
				X = x + i
				Y = y + j
				if self.isValid(X, Y, N) and (X, Y) not in seen:
					seen[X, Y] = True
					queue.append([X, Y, d + 1])
		return -1


class Solution:

	def minStepToReachTarget(self, kp, tp, n):
		if tp == kp:
			return 0
		kp[0] -= 1
		kp[1] -= 1
		tp[0] -= 1
		tp[1] -= 1
		poss = [[1, 2], [2, 1], [-1, -2], [-2, -1], [1, -2], [-1, 2], [2, -1], [-2, 1]]
		q = [kp]
		ptr = 0
		level = 0
		visited = [[False for i in range(n)] for j in range(n)]
		visited[kp[0]][kp[1]] = True
		while ptr < len(q):
			if q[ptr] == tp:
				return level
			level += 1
			for _ in range(len(q) - ptr):
				top = q[ptr]
				ptr += 1
				for i in poss:
					a = top[0] + i[0]
					b = top[1] + i[1]
					if a >= 0 and a < n and (b >= 0) and (b < n) and (not visited[a][b]):
						if [a, b] == tp:
							return level
						q.append([a, b])
						visited[a][b] = True
		return -1


from collections import deque

class Solution:

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

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		visited = [[False for _ in range(N)] for _ in range(N)]
		distance = [[-1 for _ in range(N)] for _ in range(N)]
		moves = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]
		visited[KnightPos[0] - 1][KnightPos[1] - 1] = True
		distance[KnightPos[0] - 1][KnightPos[1] - 1] = 0
		q = deque()
		q.append((KnightPos[0] - 1, KnightPos[1] - 1))
		while len(q) > 0:
			t = q.popleft()
			if t[0] == TargetPos[0] - 1 and t[1] == TargetPos[1] - 1:
				break
			for move in moves:
				nx = t[0] + move[0]
				ny = t[1] + move[1]
				if not self.isValid(nx, ny, N):
					continue
				if visited[nx][ny]:
					continue
				distance[nx][ny] = distance[t[0]][t[1]] + 1
				q.append((nx, ny))
				visited[nx][ny] = True
		return distance[TargetPos[0] - 1][TargetPos[1] - 1]


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		from collections import deque
		(SrcX, SrcY) = (KnightPos[0] - 1, KnightPos[1] - 1)
		(TargetX, TargetY) = (TargetPos[0] - 1, TargetPos[1] - 1)
		Queue = deque()
		Directions = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [1, -2], [-1, 2], [-1, -2]]
		Visited = []
		for i in range(0, N):
			temp = [0] * N
			Visited.append(temp)
		Queue.append([SrcX, SrcY, 0])
		Visited[SrcX][SrcY] = 1
		while len(Queue) != 0:
			top = Queue.popleft()
			if top[0] == TargetX and top[1] == TargetY:
				return top[2]
			else:
				for i in range(0, len(Directions)):
					Row = top[0] + Directions[i][0]
					Col = top[1] + Directions[i][1]
					Dist = top[2] + 1
					if Row >= 0 and Row < N and (Col >= 0) and (Col < N) and (Visited[Row][Col] == 0):
						Visited[Row][Col] = 1
						Queue.append([Row, Col, Dist])
		return -1


from collections import deque

class Solution:

	def minStepToReachTarget(self, start, target, N):
		(ti, tj) = target
		que = deque([start])
		level = 0
		visited = [[False for _ in range(N + 1)] for _ in range(N + 1)]
		visited[start[0]][start[1]] = True
		while que:
			for _ in range(len(que)):
				(ci, cj) = que.popleft()
				if ci == ti and cj == tj:
					return level
				for (ni, nj) in self.get_nbrs(ci, cj, N):
					if not visited[ni][nj]:
						visited[ni][nj] = True
						que.append((ni, nj))
			level += 1
		return -1

	def get_nbrs(self, pi, pj, n):
		res = []
		for (di, dj) in [(-2, 1), (-2, -1), (2, 1), (2, -1), (-1, 2), (-1, -2), (1, 2), (1, -2)]:
			if 1 <= pi + di <= n and 1 <= pj + dj <= n:
				res.append((pi + di, pj + dj))
		return res


from collections import deque

class point:

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

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		visited = [[0] * N for i in range(N)]
		KnightPos[0] -= 1
		KnightPos[1] -= 1
		TargetPos[0] -= 1
		TargetPos[1] -= 1
		que = deque()
		p1 = point(KnightPos[0], KnightPos[1], 0)
		que.append(p1)
		visited[KnightPos[0]][KnightPos[1]] = True
		x = [2, 2, -2, -2, 1, 1, -1, -1]
		y = [1, -1, 1, -1, 2, -2, 2, -2]

		def isvalid(x, y):
			return x >= 0 and y >= 0 and (x < N) and (y < N) and (not visited[x][y])
		while que:
			p = que.popleft()
			if p.x == TargetPos[0] and p.y == TargetPos[1]:
				return p.d
			for i in range(8):
				if isvalid(p.x + x[i], p.y + y[i]):
					p1 = point(p.x + x[i], p.y + y[i], p.d + 1)
					que.append(p1)
					visited[p1.x][p1.y] = True
		return -1


class Solution:

	def valid(self, x, y, m, n):
		if x < 0 or x >= m or y < 0 or (y >= n):
			return False
		else:
			return True

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		directions = [[2, -1], [2, 1], [-2, 1], [-2, -1], [1, 2], [-1, 2], [1, -2], [-1, -2]]
		m = N
		n = N
		queue = [(KnightPos[0] - 1, KnightPos[1] - 1, 0)]
		seen = {(KnightPos[0] - 1, KnightPos[1] - 1)}
		while len(queue) != 0:
			(x, y, t) = queue.pop(0)
			if x == TargetPos[0] - 1 and y == TargetPos[1] - 1:
				return t
			for (dx, dy) in directions:
				(X, Y) = (x + dx, y + dy)
				if self.valid(X, Y, m, n) and (X, Y) not in seen:
					seen.add((X, Y))
					queue.append((X, Y, t + 1))
		return -1


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		if N <= 0:
			return
		directions = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]
		q = deque([(KnightPos[0], KnightPos[1], 0)])
		visited = set()
		visited.add((KnightPos[0], KnightPos[1]))
		while q:
			(cur_x, cur_y, steps) = q.popleft()
			if cur_x == TargetPos[0] and cur_y == TargetPos[1]:
				return steps
			for (dx, dy) in directions:
				new_x = cur_x + dx
				new_y = cur_y + dy
				if new_x <= N and new_x > 0 and (new_y <= N) and (new_y > 0) and ((new_x, new_y) not in visited):
					visited.add((new_x, new_y))
					q.append((new_x, new_y, steps + 1))
		return -1


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		q = []
		(a, b) = KnightPos
		(d, e) = TargetPos
		q.append((a, b))
		level = [[-1] * (N + 1) for i in range(N + 1)]
		level[a][b] = 0
		if a == d and b == e:
			return 0
		while q:
			(i, j) = q.pop(0)
			dirs = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]
			for (a, b) in dirs:
				if i + a >= 1 and j + b >= 1 and (i + a <= N) and (j + b <= N) and (level[i + a][j + b] == -1):
					q.append((i + a, j + b))
					level[i + a][j + b] = level[i][j] + 1
					if d == i + a and e == j + b:
						return level[i + a][j + b]
		return -1


class Solution:

	def minStepToReachTarget(self, S, Target, N):
		S = [S[0] - 1, S[1] - 1]
		Target = [Target[0] - 1, Target[1] - 1]
		dx = [-1, -2, -2, -1, 1, 2, 2, 1]
		dy = [-2, -1, 1, 2, 2, 1, -1, -2]
		visited = [[0 for i in range(N)] for i in range(N)]
		queue = [(0, S[0], S[1])]
		visited[S[0]][S[1]] = 1
		while queue:
			(d, r, c) = queue.pop(0)
			if r == Target[0] and c == Target[1]:
				return d
			for i in range(8):
				(x, y) = (r + dx[i], c + dy[i])
				if x >= 0 and y >= 0 and (x < N) and (y < N) and (visited[x][y] == 0):
					visited[x][y] = 1
					queue.append((d + 1, x, y))


class Node:

	def __init__(self, row, col, step):
		self.row = row
		self.col = col
		self.step = step

class Solution:

	def is_valid(self, x, y, n, visited):
		if x >= 1 and x <= N and (y >= 1) and (y <= N) and (visited[x][y] == 0):
			return True
		return False

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		start_pos = Node(KnightPos[0], KnightPos[1], 0)
		end_pos = Node(TargetPos[0], TargetPos[1], 0)
		x_move = [2, 2, -2, -2, 1, 1, -1, -1]
		y_move = [1, -1, 1, -1, 2, -2, 2, -2]
		visited = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
		visited[start_pos.row][start_pos.col] = 1
		queue = []
		queue.append(start_pos)
		while len(queue):
			pos = queue.pop(0)
			if pos.row == end_pos.row and pos.col == end_pos.col:
				return pos.step
			for i in range(8):
				x = pos.row + x_move[i]
				y = pos.col + y_move[i]
				if self.is_valid(x, y, N, visited):
					node = Node(x, y, pos.step + 1)
					visited[x][y] = 1
					queue.append(node)
		return -1


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		q = deque()
		q.append(KnightPos)
		jump = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [1, -2], [-1, 2], [-1, -2]]
		cnt = -1
		visited = [[0] * (N + 1) for i in range(N + 1)]
		visited[KnightPos[0]][KnightPos[1]] = 1
		while q:
			cnt += 1
			q_len = len(q)
			for i in range(q_len):
				pos = q.popleft()
				if pos == TargetPos:
					return cnt
				for (x, y) in jump:
					if 0 < x + pos[0] <= N and 0 < y + pos[1] <= N and (visited[x + pos[0]][y + pos[1]] == 0):
						visited[x + pos[0]][y + pos[1]] = 1
						q.append([x + pos[0], y + pos[1]])
		return -1


from collections import deque

def isInside(i, j, n, m):
	if i >= 0 and i < n and (j >= 0) and (j < m):
		return True
	return False

def getAvailableNeighbors(i, j, n, m):
	dx = [-1, 1, -2, 2, -2, 2, -1, 1]
	dy = [-2, -2, -1, -1, 1, 1, 2, 2]
	avail = []
	for w in range(len(dy)):
		x = i + dx[w]
		y = j + dy[w]
		if isInside(x, y, n, m):
			avail.append((x, y))
	return avail

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		visited = [[False] * N for i in range(N)]
		q = deque()
		ct = 0
		q.append((KnightPos[0] - 1, KnightPos[1] - 1, ct))
		while q:
			r = q.popleft()
			if r[0] == TargetPos[0] - 1 and r[1] == TargetPos[1] - 1:
				return r[2]
			visited[r[0]][r[1]] = True
			neighs = getAvailableNeighbors(r[0], r[1], N, N)
			for neigh in neighs:
				if not visited[neigh[0]][neigh[1]]:
					q.append((neigh[0], neigh[1], r[2] + 1))
					visited[neigh[0]][neigh[1]] = True


class Solution:

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

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		dx = [2, 2, -2, -2, 1, 1, -1, -1]
		dy = [1, -1, 1, -1, 2, -2, 2, -2]
		queue = []
		queue.append(Solution(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 self.isInside(x, y, N) and (not visited[x][y]):
					visited[x][y] = True
					queue.append(Solution(x, y, t.dist + 1))

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


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		if KnightPos == TargetPos:
			return 0
		next1 = [[-1, 2], [-2, 1], [-2, -1], [-1, -2], [1, -2], [2, -1], [2, 1], [1, 2]]
		q = deque([[KnightPos[0], KnightPos[1], 0]])
		(pos, len1) = (0, 1)
		visited = {(KnightPos[0], KnightPos[1])}
		while q:
			(x, y, steps) = q.popleft()
			for (x1, y1) in next1:
				(x2, y2) = (x + x1, y + y1)
				if [x2, y2] == TargetPos:
					return steps + 1
				if -1 < x2 < N and -1 < y2 < N and ((x2, y2) not in visited):
					q.append([x2, y2, steps + 1])
					visited.add((x2, y2))
		return -1


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		if KnightPos == TargetPos:
			return 0
		next1 = [[-1, 2], [-2, 1], [-2, -1], [-1, -2], [1, -2], [2, -1], [2, 1], [1, 2]]
		q = deque()
		q.append([KnightPos[0], KnightPos[1], 0])
		(pos, len1) = (0, 1)
		visited = {(KnightPos[0], KnightPos[1])}
		while pos < len1:
			(x, y, steps) = q.popleft()
			for (x1, y1) in next1:
				x2 = x + x1
				y2 = y + y1
				if [x2, y2] == TargetPos:
					return steps + 1
				if -1 < x2 < N and -1 < y2 < N and ((x2, y2) not in visited):
					q.append([x2, y2, steps + 1])
					visited.add((x2, y2))
					len1 += 1
			pos += 1
		return -1

	def minStepToReachTarget1(self, KnightPos, TargetPos, N):
		queue = deque()
		queue.append([[KnightPos[0], KnightPos[1]], 0])
		visited = [[0 for i in range(N + 1)] for j in range(N + 1)]
		delrow = [-1, 1, -1, 1, 2, -2, 2, -2]
		delcol = [2, 2, -2, -2, 1, 1, -1, -1]
		while queue:
			ele = queue.popleft()
			row = ele[0][0]
			col = ele[0][1]
			steps = ele[1]
			if row == TargetPos[0] and col == TargetPos[1]:
				return steps
			for i in range(0, 8):
				nrow = row + delrow[i]
				ncol = col + delcol[i]
				if nrow > 0 and nrow <= N and (ncol > 0) and (ncol <= N) and (visited[nrow][ncol] == 0):
					queue.append([[nrow, ncol], steps + 1])
					visited[nrow][ncol] = 1
		return -1


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		queue = deque()
		queue.append([[KnightPos[0], KnightPos[1]], 0])
		visited = [[0 for i in range(N + 1)] for j in range(N + 1)]
		delrow = [-1, 1, -1, 1, 2, -2, 2, -2]
		delcol = [2, 2, -2, -2, 1, 1, -1, -1]
		while queue:
			ele = queue.popleft()
			row = ele[0][0]
			col = ele[0][1]
			steps = ele[1]
			if row == TargetPos[0] and col == TargetPos[1]:
				return steps
			for i in range(0, 8):
				nrow = row + delrow[i]
				ncol = col + delcol[i]
				if nrow > 0 and nrow <= N and (ncol > 0) and (ncol <= N) and (visited[nrow][ncol] == 0):
					queue.append([[nrow, ncol], steps + 1])
					visited[nrow][ncol] = 1
		return -1


class Solution:

	def getKnightDirections(self):
		return [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, -2), (-1, -2), (1, 2), (-1, 2)]

	def isValidNode(self, node, N):
		if node[0] < 0 or node[0] >= N or node[1] < 0 or (node[1] >= N):
			return False
		return True

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		KnightPos = (KnightPos[0] - 1, KnightPos[1] - 1)
		TargetPos = (TargetPos[0] - 1, TargetPos[1] - 1)
		queue = [(KnightPos, 0)]
		visited = [[0] * N for _ in range(N)]
		visited[KnightPos[0]][KnightPos[1]] = 1
		min_steps = -1
		while len(queue):
			(node, steps) = queue.pop(0)
			if node[0] == TargetPos[0] and node[1] == TargetPos[1]:
				min_steps = steps
				break
			for direc in self.getKnightDirections():
				new_position = (node[0] + direc[0], node[1] + direc[1])
				if self.isValidNode(new_position, N) and visited[new_position[0]][new_position[1]] == 0:
					visited[new_position[0]][new_position[1]] = 1
					queue.append((new_position, steps + 1))
		return min_steps


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		(x, y) = (KnightPos[0] - 1, KnightPos[1] - 1)
		(t1, t2) = (TargetPos[0] - 1, TargetPos[1] - 1)
		vis = [[0 for i in range(N + 1)] for j in range(N + 1)]
		vis[x][y] = 1
		q = deque([])
		q.append((x, y))
		moves = [[1, 2], [2, 1], [-1, 2], [-2, 1], [-1, -2], [-2, -1], [1, -2], [2, -1]]
		ans = 0
		if x == t1 and y == t2:
			return ans
		while q:
			ans += 1
			n = len(q)
			for i in range(n):
				(row, col) = q.popleft()
				if row == t1 and col == t2:
					return ans - 1
				for (i, j) in moves:
					nrow = row + i
					ncol = col + j
					if nrow >= 0 and nrow < N and (ncol >= 0) and (ncol < N) and (vis[nrow][ncol] == 0):
						q.append((nrow, ncol))
						vis[nrow][ncol] = 1
		return ans


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		if KnightPos[0] == TargetPos[0] and KnightPos[1] == TargetPos[1]:
			return 0
		visited = [[0] * N for i in range(N)]
		queue = [(KnightPos[0] - 1, KnightPos[1] - 1)]
		visited[KnightPos[0] - 1][KnightPos[1] - 1] = 1
		delRow = [-1, -1, 1, 1, -2, -2, 2, 2]
		delCol = [-2, 2, -2, 2, 1, -1, 1, -1]
		count = -1
		while queue:
			size = len(queue)
			count += 1
			for i in range(size):
				(row, col) = queue.pop(0)
				if row == TargetPos[0] - 1 and col == TargetPos[1] - 1:
					return count
				for i in range(8):
					nr = row + delRow[i]
					nc = col + delCol[i]
					if nr >= 0 and nr < N and (nc >= 0) and (nc < N) and (visited[nr][nc] == 0):
						queue.append((nr, nc))
						visited[nr][nc] = 1
		return 0


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		x1 = KnightPos[0] - 1
		y1 = KnightPos[1] - 1
		x2 = TargetPos[0] - 1
		y2 = TargetPos[1] - 1
		moves = [[-2, -1], [-2, 1], [2, -1], [2, 1], [1, -2], [1, 2], [-1, -2], [-1, 2]]
		visit = set()
		que = [(x1, y1, 0)]
		while que:
			(i, j, steps) = que.pop(0)
			if i == x2 and j == y2:
				return steps
			for move in moves:
				x = i + move[0]
				y = j + move[1]
				if 0 <= x < N and 0 <= y < N and ((x, y) not in visit):
					visit.add((x, y))
					que.append((x, y, steps + 1))
		return -1


def minKnightSteps(n, KnightPos, TargetPos):
	targetX = TargetPos[0]
	targetY = TargetPos[1]
	knight_X = KnightPos[0]
	knight_Y = KnightPos[1]
	visited = {}
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			visited[i, j] = False
	x_moves = [2, 2, -2, -2, 1, 1, -1, -1]
	y_moves = [1, -1, 1, -1, 2, -2, 2, -2]
	q1 = [(knight_X, knight_Y)]
	q2 = []
	level = 0
	visited[knight_X, knight_Y] = True
	while len(q1) or len(q2):
		while len(q1):
			k = q1.pop()
			if k == TargetPos:
				return level
			for i in range(8):
				x = k[0] + x_moves[i]
				y = k[1] + y_moves[i]
				if x == targetX and y == targetY:
					return level + 1
				if x > 0 and y > 0 and (x <= n) and (y <= n) and (visited[x, y] == False):
					visited[x, y] = True
					q2.insert(0, (x, y))
		else:
			level = level + 1
		while len(q2):
			k = q2.pop()
			if k == TargetPos:
				return level
			for i in range(8):
				x = k[0] + x_moves[i]
				y = k[1] + y_moves[i]
				if x == targetX and y == targetY:
					return level + 1
				if x > 0 and y > 0 and (x <= n) and (y <= n) and (visited[x, y] == False):
					visited[x, y] = True
					q1.insert(0, (x, y))
		else:
			level = level + 1
	return level

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		if N == 1:
			return 0
		return minKnightSteps(N, KnightPos, TargetPos)


class Solution:

	def isValid(self, l, b, N):
		return l >= 0 and b >= 0 and (l < N) and (b < N)

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		directions = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [1, -2], [-1, 2], [-1, -2]]
		q = []
		vis = [[None for y in range(N)] for x in range(N)]
		vis[KnightPos[0] - 1][KnightPos[1] - 1] = 1
		q.append([KnightPos[0] - 1, KnightPos[1] - 1, 0])
		while len(q) > 0:
			x = q.pop(0)
			if x[0] == TargetPos[0] - 1 and TargetPos[1] - 1 == x[1]:
				return x[2]
			for i in range(len(directions)):
				l = x[0] + directions[i][0]
				b = x[1] + directions[i][1]
				d = x[2] + 1
				if not self.isValid(l, b, N) or vis[l][b] == 1:
					continue
				vis[l][b] = 1
				q.append([l, b, d])
		return -1


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		initialX = KnightPos[0] - 1
		initialY = KnightPos[1] - 1
		targetX = TargetPos[0] - 1
		targetY = TargetPos[1] - 1
		if initialX == targetX and initialY == targetY:
			return 0
		numSteps = 0
		visited = [[False for j in range(N)] for i in range(N)]
		visited[initialX][initialY] = True
		q = []
		q.append([initialX, initialY])
		directions = [[1, 2], [1, -2], [-1, 2], [-1, -2], [2, 1], [2, -1], [-2, 1], [-2, -1]]
		while len(q) > 0:
			numSteps += 1
			for i in range(len(q)):
				(x, y) = q.pop(0)
				for (dx, dy) in directions:
					X = x + dx
					Y = y + dy
					if X == targetX and Y == targetY:
						return numSteps
					if X >= 0 and X < N and (Y >= 0) and (Y < N) and (visited[X][Y] == False):
						q.append([X, Y])
						visited[X][Y] = True
		return -1


import collections

class Solution:

	def minStepToReachTarget(self, src, des, N):
		vis = set()
		q = collections.deque([])
		q.append((0, src[0] - 1, src[1] - 1))
		vis.add((src[0] - 1, src[1] - 1))
		c = 0
		r = [2, 2, -2, -2, 1, 1, -1, -1]
		cols = [1, -1, 1, -1, 2, -2, 2, -2]
		while q:
			e = q.popleft()
			d = e[0]
			row = e[1]
			col = e[2]
			if row == des[0] - 1 and col == des[1] - 1:
				return d
			for i in range(8):
				newr = row + r[i]
				newc = col + cols[i]
				if newc >= 0 and newr >= 0 and (newr < N) and (newc < N) and ((newr, newc) not in vis):
					q.append((d + 1, newr, newc))
					vis.add((newr, newc))
			c += 1
		return -1


import collections

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		TargetPos = [TargetPos[0] - 1, TargetPos[1] - 1]
		visited = set()
		queue = collections.deque()
		queue.append(tuple([KnightPos[0] - 1, KnightPos[1] - 1, 0]))
		visited.add(tuple([KnightPos[0] - 1, KnightPos[1] - 1, 0]))

		def add_next_field(i, j, steps):
			if i < 0 or j < 0 or i >= N or (j >= N) or (tuple([i, j]) in visited):
				return
			visited.add(tuple([i, j]))
			queue.append([i, j, steps + 1])
		while queue:
			(i, j, steps) = queue.popleft()
			if [i, j] == TargetPos:
				return steps
			add_next_field(i + 2, j + 1, steps)
			add_next_field(i + 2, j - 1, steps)
			add_next_field(i - 2, j + 1, steps)
			add_next_field(i - 2, j - 1, steps)
			add_next_field(i + 1, j + 2, steps)
			add_next_field(i + 1, j - 2, steps)
			add_next_field(i - 1, j + 2, steps)
			add_next_field(i - 1, j - 2, steps)
		return -1


from heapq import *

class Solution:

	def is_valid(self, x, y, visited, N):
		if x < 0 or y < 0 or x >= N or (y >= N) or visited[x][y]:
			return False
		return True

	def BFS(self, node, TargetPos, N):
		(u, v) = node
		bag = []
		visited = [[False for i in range(0, N)] for j in range(0, N)]
		graph = [[10 ** 8 + 1 for i in range(0, N)] for j in range(0, N)]
		bag.append([0, node])
		cur_d = 0
		while bag:
			(d, ch) = bag.pop(0)
			if ch[0] == TargetPos[0] and ch[1] == TargetPos[1]:
				return d
			for (x, y) in [[1, 2], [-1, 2], [2, 1], [-2, 1], [-1, -2], [1, -2], [2, -1], [-2, -1]]:
				cur_x = ch[0] + x
				cur_y = ch[1] + y
				cur_d = d + 1
				if self.is_valid(cur_x, cur_y, visited, N):
					visited[cur_x][cur_y] = True
					bag.append([cur_d, [cur_x, cur_y]])
		return -1

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		if KnightPos == TargetPos:
			return 0
		KnightPos = (KnightPos[0] - 1, KnightPos[1] - 1)
		TargetPos = (TargetPos[0] - 1, TargetPos[1] - 1)
		return self.BFS(KnightPos, TargetPos, N)


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		xi = KnightPos[0]
		yi = KnightPos[1]
		xf = TargetPos[0]
		yf = TargetPos[1]
		dx = [-2, -2, -1, 1, 2, 2, 1, -1]
		dy = [-1, 1, 2, 2, 1, -1, -2, -2]
		if xi == xf and yi == yf:
			return 0
		a = [[0 for i in range(N + 1)] for i in range(N + 1)]
		q = deque()
		q.append([xi, yi])
		while q:
			p = q.popleft()
			x = p[0]
			y = p[1]
			if x == xf and y == yf:
				return a[xf][yf]
			for i in range(8):
				if x + dx[i] >= 1 and y + dy[i] >= 1 and (x + dx[i] <= N) and (y + dy[i] <= N) and (a[x + dx[i]][y + dy[i]] == 0):
					a[x + dx[i]][y + dy[i]] = a[x][y] + 1
					q.append([x + dx[i], y + dy[i]])


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		sx = KnightPos[0] - 1
		sy = KnightPos[1] - 1
		tx = TargetPos[0] - 1
		ty = TargetPos[1] - 1
		board = [[0 for _ in range(N)] for _ in range(N)]
		tempx = [-2, 2, -1, 1, -2, 2, -1, 1]
		tempy = [1, 1, 2, 2, -1, -1, -2, -2]
		q = [(sx, sy, 0)]
		board[sx][sy] = 1
		while q:
			temp = q.pop(0)
			sx = temp[0]
			sy = temp[1]
			steps = temp[2]
			if sx == tx and sy == ty:
				return steps
			for i in range(8):
				newx = sx + tempx[i]
				newy = sy + tempy[i]
				if self.canVisit(board, newx, newy, N):
					board[newx][newy] = 1
					q.append((newx, newy, steps + 1))
		return -1

	def canVisit(self, board, curx, cury, n):
		if curx >= 0 and curx < n and (cury >= 0) and (cury < n) and (board[curx][cury] == 0):
			return True
		else:
			return False


FRAMESIZ = 2

def getij(x, y, n):
	j = x - 1 + FRAMESIZ
	i = n - y + FRAMESIZ
	return (i, j)
import numpy as np
dr = [(-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2)]
GRD = -1
NIL = 0
VZT = 1
from itertools import product

def makeboard(n):
	siz = FRAMESIZ + n + FRAMESIZ
	brd = np.full((siz, siz), GRD, dtype=int)
	R = range(FRAMESIZ, FRAMESIZ + n)
	for ij in product(R, R):
		brd[ij] = NIL
	return brd
from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		KnightPos = getij(*KnightPos, N)
		TargetPos = getij(*TargetPos, N)
		brd = makeboard(N)
		brd[KnightPos] = VZT
		deq = deque([(KnightPos, 0)])
		while len(deq):
			n = len(deq)
			for _ in range(n):
				((i0, j0), d) = deq.popleft()
				if (i0, j0) == TargetPos:
					return d
				for (di, dj) in dr:
					i = i0 + di
					j = j0 + dj
					if brd[i, j] == NIL:
						brd[i, j] = VZT
						deq.append(((i, j), d + 1))
		return -1


class Solution:

	def minStepToReachTarget(self, pos, target, n):
		q = [(pos[0], pos[1], 0)]
		dirn = [(2, 1), (2, -1), (1, 2), (1, -2), (-2, 1), (-2, -1), (-1, 2), (-1, -2)]
		vis = set([(pos[0], pos[1])])
		while q:
			(x, y, d) = q.pop(0)
			if [x, y] == target:
				return d
			for (dx, dy) in dirn:
				if 0 < x + dx <= n and 0 < y + dy <= n and ((x + dx, y + dy) not in vis):
					q.append((x + dx, y + dy, d + 1))
					vis.add((x + dx, y + dy))


from collections import deque

class Solution:

	def isValid(self, newxx, newyy, vis, N):
		if newxx >= 0 and newxx < N and (newyy < N) and (newyy >= 0) and (vis[newxx][newyy] != True):
			return True
		return False

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		n = N
		q = deque()
		tX = TargetPos[0] - 1
		tY = TargetPos[1] - 1
		kX = KnightPos[0] - 1
		kY = KnightPos[1] - 1
		if kX == tX and kY == tY:
			return 0
		vis = [[False for i in range(N)] for j in range(N)]
		q.append([kX, kY])
		vis[kX][kY] = True
		ans = 0
		x8 = [1, 2, 2, 1, -1, -2, -2, -1]
		y8 = [-2, -1, 1, 2, 2, 1, -1, -2]
		while q:
			size = len(q)
			ans += 1
			for i in range(size):
				temp = q.popleft()
				xx = temp[0]
				yy = temp[1]
				for i in range(8):
					newxx = xx + x8[i]
					newyy = yy + y8[i]
					if newxx == tX and newyy == tY:
						return ans
					if self.isValid(newxx, newyy, vis, N):
						q.append([newxx, newyy])
						vis[newxx][newyy] = True
		return ans


from collections import deque

class Solution:

	def __init__(self) -> None:
		self.distances = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [1, -2], [-1, 2], [-1, -2]]

	def checkPosition(self, x, y, n):
		return x < n and y < n and (x >= 0) and (y >= 0)

	def minStepToReachTarget(self, KnightPos, TargetPos, n):
		ans = -1
		queue = deque()
		visited = [[0 for i in range(n)] for j in range(n)]
		queue.append([KnightPos[0] - 1, KnightPos[1] - 1, 0])
		visited[KnightPos[0] - 1][KnightPos[1] - 1] = 1
		while len(queue):
			(node_x, node_y, step_count) = queue.popleft()
			if node_x == TargetPos[0] - 1 and node_y == TargetPos[1] - 1:
				ans = step_count
				break
			for move in self.distances:
				if self.checkPosition(node_x + move[0], node_y + move[1], n) and (not visited[node_x + move[0]][node_y + move[1]]):
					queue.append([node_x + move[0], node_y + move[1], step_count + 1])
					visited[node_x + move[0]][node_y + move[1]] = 1
		return ans


from collections import deque

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		if KnightPos == TargetPos:
			return 0
		visited = [[False] * N for _ in range(N)]
		q = deque()
		moves = [[1, 2], [2, 1], [-1, 2], [2, -1], [1, -2], [-2, 1], [-1, -2], [-2, -1]]
		q.append(KnightPos)
		visited[KnightPos[0] - 1][KnightPos[1] - 1] = True
		steps = 0
		while len(q):
			for _ in range(len(q)):
				(x, y) = q.popleft()
				for (mx, my) in moves:
					(nx, ny) = (x + mx, y + my)
					if nx > 0 and nx <= N and (ny > 0) and (ny <= N) and (visited[nx - 1][ny - 1] == False):
						if [nx, ny] == TargetPos:
							return steps + 1
						visited[nx - 1][ny - 1] = True
						q.append([nx, ny])
			steps += 1
		return -1


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		directions = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [1, -2], [-1, 2], [-1, -2]]
		KnightPos.append(0)
		queue = []
		queue.append(KnightPos)
		ans = 0
		level = 0
		visited = [[0] * (N + 1) for i in range(N + 1)]
		visited[KnightPos[0]][KnightPos[1]] = 1
		while queue:
			v = queue.pop(0)
			if v[0] == TargetPos[0] and v[1] == TargetPos[1]:
				ans = v[2]
				break
			else:
				x = v[0]
				y = v[1]
				for i in directions:
					if i[0] + x >= 1 and i[0] + x <= N and (i[1] + y >= 1) and (i[1] + y <= N) and (visited[i[0] + x][i[1] + y] == 0):
						visited[i[0] + x][i[1] + y] = 1
						queue.append([i[0] + x, i[1] + y, v[2] + 1])
		return ans


from collections import deque

class Solution:

	def minStepToReachTarget(self, kp, tp, N):
		if kp[0] < 1 or kp[1] < 1 or kp[0] > N or (kp[1] > N):
			return -1
		moves = ((1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1))
		visited = set()
		queue = deque()
		queue.append(tuple(kp))
		visited.add(tuple(kp))
		path = {tuple(kp): 'None'}
		req = tuple(tp)
		while queue:
			temp = queue.popleft()
			if temp == req:
				break
			for (i, j) in moves:
				(x, y) = (temp[0] + i, temp[1] + j)
				if isvalid(x, y, N) and (x, y) not in visited:
					visited.add((x, y))
					queue.append((x, y))
					path[x, y] = temp
		count = -1
		while temp in path:
			count += 1
			temp = path[temp]
		return count

def isvalid(x, y, n):
	return x > 0 and y > 0 and (x <= N) and (y <= N)


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		grid = [[0 for _ in range(N + 1)] for __ in range(N + 1)]
		vis = [[0 for _ in range(N + 1)] for __ in range(N + 1)]
		q = [[KnightPos, 0]]
		return self.bfs(vis, grid, q, TargetPos)

	def bfs(self, vis, grid, q, TargetPos):
		while q:
			x = q.pop(0)
			r = x[0][0]
			c = x[0][1]
			l = x[1]
			vis[r][c] = 1
			if r == TargetPos[0] and c == TargetPos[1]:
				return l
			de = [[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 i in de:
				ro = i[0]
				co = i[1]
				if ro >= 0 and co >= 0 and (ro < len(grid)) and (co < len(grid[0])) and (vis[ro][co] != 1):
					q.append([[ro, co], l + 1])
					vis[ro][co] = 1
		return -1


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		xs = [-1, -1, -2, -2, 2, 2, 1, 1]
		ys = [2, -2, -1, 1, 1, -1, 2, -2]
		(x, y) = KnightPos
		queue = [(x, y, 0)]
		visited = set()
		visited.add((x, y))
		while queue:
			(x, y, n_step) = queue.pop(0)
			if x == TargetPos[0] and y == TargetPos[1]:
				return n_step
			for (dx, dy) in zip(xs, ys):
				(new_x, new_y) = (x + dx, y + dy)
				if 0 < new_x <= N and 0 < new_y <= N and ((new_x, new_y) not in visited):
					queue.append((new_x, new_y, n_step + 1))
					visited.add((new_x, new_y))
		return -1


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		from collections import deque
		KnightPos[:] = [KnightPos[0] - 1, KnightPos[1] - 1]
		TargetPos[:] = [TargetPos[0] - 1, TargetPos[1] - 1]
		qu = deque([KnightPos])
		M = [[float('inf') for i in range(N)] for j in range(N)]
		M[KnightPos[0]][KnightPos[1]] = 0
		dx = [-2, -1, 1, 2]
		dy = [-2, -1, 1, 2]
		visited = [[0 for i in range(N)] for j in range(N)]
		visited[KnightPos[0]][KnightPos[1]] = 1
		while len(qu) != 0:
			point = qu.popleft()
			i = point[0]
			j = point[1]
			if i == TargetPos[0] and j == TargetPos[1]:
				return M[i][j]
			for p in dx:
				for q in dy:
					if abs(p) == abs(q):
						continue
					x = i + p
					y = j + q
					if x < N and y < N and (x >= 0) and (y >= 0) and (not visited[x][y]):
						visited[x][y] = 1
						M[x][y] = min(M[x][y], M[i][j] + 1)
						qu.append([x, y])
		return -1


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		min_c = 10 ** 10

		def is_valid(i, j, N, visited):
			if i >= 0 and i < N and (j >= 0) and (j < N) and ((i, j) not in visited):
				return True
			return False
		x1 = KnightPos[0] - 1
		y1 = KnightPos[1] - 1
		x2 = TargetPos[0] - 1
		y2 = TargetPos[1] - 1
		moves = [[-2, -1], [-2, 1], [2, -1], [2, 1], [1, -2], [1, 2], [-1, -2], [-1, 2]]
		visited = set()
		queue = [(x1, y1, 0)]
		while queue:
			(i, j, steps) = queue.pop(0)
			if i == x2 and j == y2:
				return steps
			for k in moves:
				x = i + k[0]
				y = j + k[1]
				if is_valid(x, y, N, visited):
					visited.add((x, y))
					queue.append((x, y, steps + 1))
		return -1


import collections

class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		rows = [2, 1, -1, -2, -2, -1, 1, 2]
		cols = [1, 2, 2, 1, -1, -2, -2, -1]
		visi = [[0 for i in range(N + 1)] for j in range(N + 1)]

		def issafe(i, j):
			if i > N or j > N or i <= 0 or (j <= 0) or (visi[i][j] == 1):
				return 0
			return 1
		q = collections.deque()
		q.append([KnightPos[0], KnightPos[1], 0])
		visi[KnightPos[0]][KnightPos[1]] = 1
		if KnightPos[0] == TargetPos[0] and KnightPos[1] == TargetPos[1]:
			return 0
		m1 = -1
		flag = 0
		while len(q) > 0:
			(x, y, wt) = q[0]
			q.popleft()
			for t in range(8):
				i = rows[t]
				j = cols[t]
				if issafe(x + i, y + j):
					q.append([x + i, y + j, wt + 1])
					visi[x + i][y + j] = 1
					m1 = wt + 1
					if x + i == TargetPos[0] and y + j == TargetPos[1]:
						flag = 1
						break
			if flag == 1:
				break
		return m1


from collections import deque

class Solution:

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

		def safe(tx, ty):
			if tx > 0 and ty > 0 and (tx <= N) and (ty <= N):
				return 1
			return 0
		visited = set()
		stack = deque()
		stack.append([KnightPos[0], KnightPos[1], 0])
		visited.add(tuple(KnightPos))
		while stack:
			(x, y, steps) = stack.popleft()
			if [x, y] == TargetPos:
				return steps
			for i in range(8):
				tx = x + dx[i]
				ty = y + dy[i]
				if safe(tx, ty) and (tx, ty) not in visited:
					visited.add((tx, ty))
					stack.append([tx, ty, steps + 1])
		return -1


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		q = []
		vis = [[0] * (N + 1) for i in range(N + 1)]
		q.append([KnightPos[0], KnightPos[1], 0])
		vis[KnightPos[0]][KnightPos[1]] = 1
		mat = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [-1, 2], [1, -2], [-1, -2]]
		while q:
			(x, y, step) = q.pop(0)
			if x == TargetPos[0] and y == TargetPos[1]:
				return step
			for (dx, dy) in mat:
				newx = x + dx
				newy = y + dy
				if newx > 0 and newx < N + 1 and (newy >= 0) and (newy < N + 1) and (not vis[newx][newy]):
					vis[newx][newy] = 1
					q.append([newx, newy, step + 1])
		return -1


class Solution:

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		n = N
		dist = [[-1 for i in range(n + 1)] for j in range(n + 1)]
		(sr, sc) = KnightPos
		(tr, tc) = TargetPos
		if sr == tr and sc == tc:
			return 0
		l1 = [KnightPos]
		dr = [2, 2, -2, -2, 1, 1, -1, -1]
		dc = [1, -1, 1, -1, 2, -2, 2, -2]
		l2 = []
		steps = 0
		while len(l1) != 0:
			for i in l1:
				(cr, cc) = i
				for j in range(8):
					nr = cr + dr[j]
					nc = cc + dc[j]
					if nr >= 1 and nr <= n and (nc >= 1) and (nc <= n):
						if dist[nr][nc] == -1:
							l2.append([nr, nc])
							dist[nr][nc] = steps + 1
							if nr == tr and nc == tc:
								return steps + 1
			l1 = l2[:]
			l2 = []
			steps += 1
		return -1


from collections import deque

class Solution:

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

		def bfs(start_x, start_y):
			q = deque([[start_x, start_y, 0]])
			directions = [[2, 1], [2, -1], [-2, -1], [-2, 1], [1, 2], [1, -2], [-1, 2], [-1, -2]]
			while q:
				(x, y, dist) = q.popleft()
				if [x + 1, y + 1] == TargetPos:
					return dist
				for (u, v) in directions:
					pos_x = u + x
					pos_y = v + y
					if 0 <= pos_x < N and 0 <= pos_y < N and (visited[pos_x][pos_y] == 0):
						visited[pos_x][pos_y] = 1
						q.append([pos_x, pos_y, dist + 1])
		visited = [[0 for _ in range(N)] for _ in range(N)]
		return bfs(KnightPos[0] - 1, KnightPos[1] - 1)


class Solution:

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

		def makeadj(i, j, N):
			l = [[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]]
			k = 0
			ans = []
			for (x, y) in l:
				if 1 <= x <= N and 1 <= y <= N:
					ans.append([x, y])
			return ans
		vis = []
		for i in range(N):
			l = []
			for j in range(N):
				l.append(0)
			vis.append(l)
		(x, y) = (KnightPos[0], KnightPos[1])
		(j, k) = (TargetPos[0], TargetPos[1])
		vis[x - 1][y - 1] = 1
		q = []
		q.append([x, y, 0])
		while q:
			(a, b, c) = q.pop(0)
			if a == j and b == k:
				return c
			l = makeadj(a, b, N)
			for (d, f) in l:
				if vis[d - 1][f - 1] == 0:
					q.append([d, f, c + 1])
					vis[d - 1][f - 1] = 1
		return -1


class Solution:

	def __init__(self):
		self.visited = []

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

	def minStepToReachTarget(self, KnightPos, TargetPos, N):
		KnightPos[0] -= 1
		KnightPos[1] -= 1
		TargetPos[0] -= 1
		TargetPos[1] -= 1
		q = []
		movements = [[2, -1], [2, 1], [-2, -1], [-2, 1], [-1, 2], [1, 2], [-1, -2], [1, -2]]
		for i in range(N):
			self.visited.append(N * [False])
		q.append([[KnightPos[0], KnightPos[1]], 0])
		self.visited[KnightPos[0]][KnightPos[1]] = True
		while q:
			cur = q.pop(0)
			if cur[0] == TargetPos:
				return cur[1]
			for m in movements:
				x = cur[0][0] + m[0]
				y = cur[0][1] + m[1]
				if self.isValid(x, y, N):
					if not self.visited[x][y]:
						q.append([[x, y], cur[1] + 1])
						self.visited[x][y] = True


class Solution:

	def minStepToReachTarget(self, k, t, N):
		t = [t[0] - 1, t[1] - 1]
		k = [k[0] - 1, k[1] - 1]
		dx = [1, -1, 2, -2, -1, 1, -2, 2]
		dy = [2, 2, 1, 1, -2, -2, -1, -1]
		visit = [[0 for i in range(N)] for j in range(N)]
		q = [(0, k[0], k[1])]
		visit[k[0]][k[1]] = 1
		while q:
			(d, r, c) = q.pop(0)
			if r == t[0] and c == t[1]:
				return d
			for i in range(8):
				x = r + dx[i]
				y = c + dy[i]
				if x >= 0 and y >= 0 and (x < N) and (y < N) and (visit[x][y] == 0):
					visit[x][y] = 1
					q.append((d + 1, x, y))


class Solution:

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

		def isValid(i, j):
			if i >= 0 and i < N and (j >= 0) and (j < N):
				return True
			else:
				return False
		directions = [[2, 1], [2, -1], [-1, -2], [-1, 2], [-2, 1], [-2, -1], [1, 2], [1, -2]]
		queue = []
		visited = [[0 for i in range(N)] for j in range(N)]
		visited[KnightPos[0] - 1][KnightPos[1] - 1] = 1
		queue.append([[KnightPos[0] - 1, KnightPos[1] - 1], 0])
		while queue:
			x = queue.pop(0)
			if x[0][0] == TargetPos[0] - 1 and x[0][1] == TargetPos[1] - 1:
				return x[1]
			for i in range(len(directions)):
				a = x[0][0] + directions[i][0]
				b = x[0][1] + directions[i][1]
				d = x[1] + 1
				if not isValid(a, b):
					continue
				if not visited[a][b]:
					visited[a][b] = 1
					queue.append([[a, b], d])
		return -1