





__lowerCAmelCase     =			float("inf")




class   _UpperCAmelCase	:




					def __init__(						self    ,      __lowerCAmelCase       )						->  Tuple:
							UpperCamelCase__         =	[0] * n
							UpperCamelCase__         =	[0] * n
							UpperCamelCase__         =	[0] * n
							UpperCamelCase__         =	[[] for _ in range(__lowerCAmelCase       )]




					def 	snake_case_		(						self    ,      __lowerCAmelCase    ,      __lowerCAmelCase    ,      __lowerCAmelCase    ,      __lowerCAmelCase=0       )						->  Union[str, Any]:
							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    ,      __lowerCAmelCase    ,      __lowerCAmelCase    ,      __lowerCAmelCase       )						->  Union[str, Any]:
							if vertex == sink or not flow:
									return flow

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




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

											UpperCamelCase__         =	self.depth_first_search(__lowerCAmelCase    ,      __lowerCAmelCase    ,      __lowerCAmelCase       )
											while p:
													flow += p
													UpperCamelCase__         =	self.depth_first_search(__lowerCAmelCase    ,      __lowerCAmelCase    ,      __lowerCAmelCase       )

											if not self.lvl[sink]:
													break

							return flow
__lowerCAmelCase     =			Dinic(10)
__lowerCAmelCase     =			0
__lowerCAmelCase     =			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))












from dataclasses import dataclass

__lowerCAmelCase     =			"0.1"
__lowerCAmelCase     =			"Lucia Harcekova"




@dataclass
class   _UpperCAmelCase	:
					__A          =   42
					__A          =   42
					__A          =   42




					def __repr__(						self       )						->  str:
							return F"""({self.offset}, {self.length}, {self.indicator})"""




class   _UpperCAmelCase	:




					def __init__(						self    ,      __lowerCAmelCase = 13    ,      __lowerCAmelCase = 6       )						->  None:
							UpperCamelCase__         =	window_size
							UpperCamelCase__         =	lookahead_buffer_size
							UpperCamelCase__         =	self.window_size - self.lookahead_buffer_size




					def 	snake_case_		(						self    ,      __lowerCAmelCase       )						->  list[Token]:
							UpperCamelCase__         =	[]
							UpperCamelCase__         =	""""""

							# while there are still characters in text to compress
							while text:
									# find the next encoding phrase
									# - triplet with offset, length, indicator (the next encoding character)
									UpperCamelCase__         =	self._find_encoding_token(__lowerCAmelCase    ,      __lowerCAmelCase       )

									# update the search buffer:
									# - add new characters from text into it
									# - check if size exceed the max search buffer size, if so, drop the
									#   oldest elements
									search_buffer += text[: token.length + 1]
									if len(__lowerCAmelCase       ) > self.search_buffer_size:
											UpperCamelCase__         =	search_buffer[-self.search_buffer_size :]

									# update the text
									UpperCamelCase__         =	text[token.length + 1 :]

									# append the token to output
									output.append(__lowerCAmelCase       )

							return output




					def 	snake_case_		(						self    ,      __lowerCAmelCase       )						->  str:
							UpperCamelCase__         =	""""""

							for token in tokens:
									for _ in range(token.length       ):
											output += output[-token.offset]
									output += token.indicator

							return output




					def 	snake_case_		(						self    ,      __lowerCAmelCase    ,      __lowerCAmelCase       )						->  Token:

							if not text:
									raise ValueError("""We need some text to work with."""       )

							# Initialise result parameters to default values
							UpperCamelCase__  ,			UpperCamelCase__         =	0, 0

							if not search_buffer:
									return Token(__lowerCAmelCase    ,      __lowerCAmelCase    ,      text[length]       )

							for i, character in enumerate(__lowerCAmelCase       ):
									UpperCamelCase__         =	len(__lowerCAmelCase       ) - i
									if character == text[0]:
											UpperCamelCase__         =	self._match_length_from_index(__lowerCAmelCase    ,      __lowerCAmelCase    ,      0    ,      __lowerCAmelCase       )
											# if the found length is bigger than the current or if it's equal,
											# which means it's offset is smaller: update offset and length
											if found_length >= length:
													UpperCamelCase__  ,			UpperCamelCase__         =	found_offset, found_length

							return Token(__lowerCAmelCase    ,      __lowerCAmelCase    ,      text[length]       )




					def 	snake_case_		(						self    ,      __lowerCAmelCase    ,      __lowerCAmelCase    ,      __lowerCAmelCase    ,      __lowerCAmelCase       )						->  int:
							if not text or text[text_index] != window[window_index]:
									return 0
							return 1 + self._match_length_from_index(
							    __lowerCAmelCase    ,      window + text[text_index]    ,      text_index + 1    ,      window_index + 1       )


if __name__ == "__main__":
				from doctest import testmod

				testmod()
				# Initialize compressor class
				__lowerCAmelCase     =			LZaaCompressor(window_size=13, lookahead_buffer_size=6)

				# Example
				__lowerCAmelCase     =			"cabracadabrarrarrad"
				__lowerCAmelCase     =			lzaa_compressor.compress(TEXT)
				print(lzaa_compressor.compress("ababcbababaa"))
				__lowerCAmelCase     =			lzaa_compressor.decompress(compressed_text)
				assert decompressed_text == TEXT, "The LZ77 algorithm returned the invalid result."





