





'''simple docstring'''

lowercase_         =			float("""inf""")


class  a_					:

    '''simple docstring'''


    def __init__(		self			,		A	)		->       Optional[Any]:
        _SCREAMING_SNAKE_CASE     =      [0] * n
        _SCREAMING_SNAKE_CASE     =      [0] * n
        _SCREAMING_SNAKE_CASE     =      [0] * n
        _SCREAMING_SNAKE_CASE     =      [[] for _ in range(A	)]


    def       snake_case_(		self			,		A			,		A			,		A			,		A=0	)		->       Dict:
        self.adj[a].append([b, len(self.adj[b]	), c, 0]	)
        self.adj[b].append([a, len(self.adj[a]	) - 1, rcap, 0]	)


    def       snake_case_(		self			,		A			,		A			,		A	)		->       int:
        if vertex == sink or not flow:
            return flow

        for i in range(self.ptr[vertex]			,		len(self.adj[vertex]	)	):
            _SCREAMING_SNAKE_CASE     =      self.adj[vertex][i]
            if self.lvl[e[0]] == self.lvl[vertex] + 1:
                _SCREAMING_SNAKE_CASE     =      self.depth_first_search(e[0]			,		A			,		min(A			,		e[2] - e[3]	)	)
                if p:
                    self.adj[vertex][i][3] += p
                    self.adj[e[0]][e[1]][3] -= p
                    return p
            _SCREAMING_SNAKE_CASE     =      self.ptr[vertex] + 1
        return 0





    def       snake_case_(		self			,		A			,		A	)		->       Optional[int]:
        _SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE     =      0, source
        for l in range(31	):  # noqa: E741  l = 30 maybe faster for random data
            while True:
                _SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE     =      [0] * len(self.q	), [0] * len(self.q	)
                _SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE     =      0, 1, 1
                while qi < qe and not self.lvl[sink]:
                    _SCREAMING_SNAKE_CASE     =      self.q[qi]
                    qi += 1
                    for e in self.adj[v]:
                        if not self.lvl[e[0]] and (e[2] - e[3]) >> (30 - l):
                            _SCREAMING_SNAKE_CASE     =      e[0]
                            qe += 1
                            _SCREAMING_SNAKE_CASE     =      self.lvl[v] + 1

                _SCREAMING_SNAKE_CASE     =      self.depth_first_search(A			,		A			,		A	)
                while p:
                    flow += p
                    _SCREAMING_SNAKE_CASE     =      self.depth_first_search(A			,		A			,		A	)

                if not self.lvl[sink]:
                    break

        return flow
lowercase_         =			Dinic(10)
lowercase_         =			0
lowercase_         =			9
for vertex in range(1, 5):
      graph.add_edge(source, vertex, 1)
for vertex in range(5, 9):
      graph.add_edge(vertex, sink, 1)
for vertex in range(1, 5):
      graph.add_edge(vertex, vertex + 4, 1)

# Now we can know that is the maximum flow(source -> sink)
print(graph.max_flow(source, sink))










'''simple docstring'''

def lowerCamelCase						(					__lowerCamelCase			:   int ,	__lowerCamelCase			:   int ,	__lowerCamelCase			:   int ,	__lowerCamelCase			:   int   )						->int:
    return len_board * len_board_column * row + column





def lowerCamelCase						(					__lowerCamelCase			:   list[list[str]] ,	__lowerCamelCase			:   str ,	__lowerCamelCase			:   int ,	__lowerCamelCase			:   int ,	__lowerCamelCase			:   int ,	__lowerCamelCase			:   set[int] ,	)						->bool:

    if board[row][column] != word[word_index]:
        return False

    if word_index == len(__lowerCamelCase   ) - 1:
        return True

    _SCREAMING_SNAKE_CASE     =      [(0, 1), (0, -1), (-1, 0), (1, 0)]
    _SCREAMING_SNAKE_CASE     =      len(__lowerCamelCase   )
    _SCREAMING_SNAKE_CASE     =      len(board[0]   )
    for direction in traverts_directions:
        _SCREAMING_SNAKE_CASE     =      row + direction[0]
        _SCREAMING_SNAKE_CASE     =      column + direction[1]
        if not (0 <= next_i < len_board and 0 <= next_j < len_board_column):
            continue

        _SCREAMING_SNAKE_CASE     =      get_point_key(__lowerCamelCase ,	__lowerCamelCase ,	__lowerCamelCase ,	__lowerCamelCase   )
        if key in visited_points_set:
            continue

        visited_points_set.add(__lowerCamelCase   )
        if exits_word(__lowerCamelCase ,	__lowerCamelCase ,	__lowerCamelCase ,	__lowerCamelCase ,	word_index + 1 ,	__lowerCamelCase   ):
            return True

        visited_points_set.remove(__lowerCamelCase   )

    return False





def lowerCamelCase						(					__lowerCamelCase			:   list[list[str]] ,	__lowerCamelCase			:   str   )						->bool:
    _SCREAMING_SNAKE_CASE     =      (
        """The board should be a non empty matrix of single chars strings."""
    )

    _SCREAMING_SNAKE_CASE     =      len(__lowerCamelCase   )
    if not isinstance(__lowerCamelCase ,	__lowerCamelCase   ) or len(__lowerCamelCase   ) == 0:
        raise ValueError(__lowerCamelCase   )

    for row in board:
        if not isinstance(__lowerCamelCase ,	__lowerCamelCase   ) or len(__lowerCamelCase   ) == 0:
            raise ValueError(__lowerCamelCase   )

        for item in row:
            if not isinstance(__lowerCamelCase ,	__lowerCamelCase   ) or len(__lowerCamelCase   ) != 1:
                raise ValueError(__lowerCamelCase   )

    # Validate word
    if not isinstance(__lowerCamelCase ,	__lowerCamelCase   ) or len(__lowerCamelCase   ) == 0:
        raise ValueError(
            """The word parameter should be a string of length greater than 0."""   )

    _SCREAMING_SNAKE_CASE     =      len(board[0]   )
    for i in range(__lowerCamelCase   ):
        for j in range(__lowerCamelCase   ):
            if exits_word(
                __lowerCamelCase ,	__lowerCamelCase ,	__lowerCamelCase ,	__lowerCamelCase ,	0 ,	{get_point_key(__lowerCamelCase ,	__lowerCamelCase ,	__lowerCamelCase ,	__lowerCamelCase   )}   ):
                return True

    return False


if __name__ == "__main__":
      import doctest

      doctest.testmod()



