






from __future__ import annotations


def __A    (      __lowerCAmelCase ,		__lowerCAmelCase	)->  list[tuple[int, int]]:





						"""simple docstring"""



						_UpperCAmelCase					, _UpperCAmelCase									=			position
						_UpperCAmelCase									=			[
						    (y + 1, x + 2),
						    (y - 1, x + 2),
						    (y + 1, x - 2),
						    (y - 1, x - 2),
						    (y + 2, x + 1),
						    (y + 2, x - 1),
						    (y - 2, x + 1),
						    (y - 2, x - 1),
						]
						_UpperCAmelCase									=			[]

						for position in positions:
												_UpperCAmelCase					, _UpperCAmelCase									=			position
												if 0 <= y_test < n and 0 <= x_test < n:
																		permissible_positions.append(__lowerCAmelCase	)

						return permissible_positions


def __A    (      __lowerCAmelCase	)->  bool:





						"""simple docstring"""



						return not any(elem == 0 for row in board for elem in row	)


def __A    (      __lowerCAmelCase ,		__lowerCAmelCase ,		__lowerCAmelCase	)->  bool:





						"""simple docstring"""



						if is_complete(__lowerCAmelCase	):
												return True

						for position in get_valid_pos(__lowerCAmelCase ,		len(__lowerCAmelCase	)	):
												_UpperCAmelCase					, _UpperCAmelCase									=			position

												if board[y][x] == 0:
																		_UpperCAmelCase									=			curr + 1
																		if open_knight_tour_helper(__lowerCAmelCase ,		__lowerCAmelCase ,		curr + 1	):
																								return True
																		_UpperCAmelCase									=			0

						return False


def __A    (      __lowerCAmelCase	)->  list[list[int]]:





						"""simple docstring"""



						_UpperCAmelCase									=			[[0 for i in range(__lowerCAmelCase	)] for j in range(__lowerCAmelCase	)]

						for i in range(__lowerCAmelCase	):
												for j in range(__lowerCAmelCase	):
																		_UpperCAmelCase									=			1
																		if open_knight_tour_helper(__lowerCAmelCase ,		(i, j) ,		1	):
																								return board
																		_UpperCAmelCase									=			0

						_UpperCAmelCase									=			F"""Open Kight Tour cannot be performed on a board of size {n}"""
						raise ValueError(__lowerCAmelCase	)


if __name__ == "__main__":
		import doctest

		doctest.testmod()






def 					UpperCAmelCase__     (   lowerCamelCase,	lowerCamelCase,	lowerCamelCase,	lowerCamelCase      ):
  # Return True if there is node that has not iterated.
  lowercase			:Union[str, Any]							=  [False] * len(lowerCamelCase      )
  lowercase			:Union[str, Any]							=  []
  queue.append(lowerCamelCase      )
  lowercase			:Optional[Any]							=  True

  while queue:
    lowercase			:Optional[Any]							=  queue.pop(0      )
    for ind in range(len(graph[u]      )      ):
      if visited[ind] is False and graph[u][ind] > 0:
        queue.append(lowerCamelCase      )
        lowercase			:Dict							=  True
        lowercase			:Dict							=  u

  return visited[t]



def 					UpperCAmelCase__     (   lowerCamelCase,	lowerCamelCase,	lowerCamelCase      ):
  # This array is filled by BFS and to store path
  lowercase			:Optional[int]							=  [-1] * (len(lowerCamelCase      ))
  lowercase			:int							=  0
  while bfs(lowerCamelCase,	lowerCamelCase,	lowerCamelCase,	lowerCamelCase      ):
    lowercase			:int							=  float("Inf"      )
    lowercase			:Any							=  sink

    while s != source:
      # Find the minimum value in select path
      lowercase			:Any							=  min(lowerCamelCase,	graph[parent[s]][s]      )
      lowercase			:Dict							=  parent[s]

    max_flow += path_flow
    lowercase			:Union[str, Any]							=  sink

    while v != source:
      lowercase			:List[Any]							=  parent[v]
      graph[u][v] -= path_flow
      graph[v][u] += path_flow
      lowercase			:Any							=  parent[v]
  return max_flow


_UpperCAmelCase		:  Optional[Any]	=   [
    [0, 16, 13, 0, 0, 0],
    [0, 0, 10, 12, 0, 0],
    [0, 4, 0, 0, 14, 0],
    [0, 0, 9, 0, 0, 20],
    [0, 0, 0, 7, 0, 4],
    [0, 0, 0, 0, 0, 0],
]

_UpperCAmelCase	,	_UpperCAmelCase		:  Any	=   0, 5







print(ford_fulkerson(graph, source, sink))



