



import numpy as np


def 	_A	(   _UpperCamelCase      ,					_UpperCamelCase="utf-8"      ,					_UpperCamelCase="surrogatepass"			):
				_UpperCAmelCase						:  str     					=	bin(int.from_bytes(text.encode(__A      ,					__A			)      ,					'''big'''			)			)[2:]
				return bits.zfill(8 * ((len(__A			) + 7) // 8)			)


def 	_A	(   _UpperCamelCase      ,					_UpperCamelCase="utf-8"      ,					_UpperCamelCase="surrogatepass"			):
				_UpperCAmelCase						:  Union[str, Any]     					=	int(__A      ,					2			)
				return n.to_bytes((n.bit_length() + 7) // 8      ,					'''big'''			).decode(__A      ,					__A			) or "\0"


def 	_A	(   _UpperCamelCase      ,					_UpperCamelCase			):
				if size_par + len(__A			) <= 2**size_par - (len(__A			) - 1):
								raise ValueError('''size of parity don\'t match with size of data'''			)

				_UpperCAmelCase						:  Any     					=	[]
				_UpperCAmelCase						:  int     					=	[]
				_UpperCAmelCase						:  Union[str, Any]     					=	[bin(__A			)[2:] for x in range(1      ,					size_par + len(__A			) + 1			)]

				# sorted information data for the size of the output data
				_UpperCAmelCase						:  int     					=	[]
				# data position template + parity
				_UpperCAmelCase						:  List[str]     					=	[]
				# parity bit counter
				_UpperCAmelCase						:  Union[str, Any]     					=	0
				# counter position of data bits
				_UpperCAmelCase						:  int     					=	0

				for x in range(1      ,					size_par + len(__A			) + 1			):
								# Performs a template of bit positions - who should be given,
								# and who should be parity
								if qtd_bp < size_par:
												if (np.log(__A			) / np.log(2			)).is_integer():
																data_out_gab.append('''P'''			)
																_UpperCAmelCase						:  Optional[int]     					=	qtd_bp + 1
												else:
																data_out_gab.append('''D'''			)
								else:
												data_out_gab.append('''D'''			)

								# Sorts the data to the new output size
								if data_out_gab[-1] == "D":
												data_ord.append(data[cont_data]			)
												cont_data += 1
								else:
												data_ord.append(__A			)

								# Calculates parity
				_UpperCAmelCase						:  List[Any]     					=	0  # parity bit counter
				for bp in range(1      ,					size_par + 1			):
								# Bit counter one for a given parity
								_UpperCAmelCase						:  str     					=	0
								# counter to control the loop reading
								_UpperCAmelCase						:  List[str]     					=	0
								for x in data_ord:
												if x is not None:
																try:
																				_UpperCAmelCase						:  str     					=	(bin_pos[cont_loop])[-1 * (bp)]
																except IndexError:
																				_UpperCAmelCase						:  Any     					=	'''0'''
																if aux == "1" and x == "1":
																				cont_bo += 1
												cont_loop += 1
								parity.append(cont_bo % 2			)

								qtd_bp += 1

				# Mount the message
				_UpperCAmelCase						:  Optional[int]     					=	0  # parity bit counter
				for x in range(0      ,					size_par + len(__A			)			):
								if data_ord[x] is None:
												data_out.append(str(parity[cont_bp]			)			)
												cont_bp += 1
								else:
												data_out.append(data_ord[x]			)

				return data_out






def 	_A	(   _UpperCamelCase      ,					_UpperCamelCase			):
				_UpperCAmelCase						:  List[str]     					=	[]
				# Parity bit counter
				_UpperCAmelCase						:  str     					=	0
				# Counter p data bit reading
				_UpperCAmelCase						:  List[str]     					=	0
				# list of parity received
				_UpperCAmelCase						:  List[Any]     					=	[]
				_UpperCAmelCase						:  Optional[int]     					=	[]

				for x in range(1      ,					len(__A			) + 1			):
								# Performs a template of bit positions - who should be given,
								#  and who should be parity
								if qtd_bp < size_par and (np.log(__A			) / np.log(2			)).is_integer():
												data_out_gab.append('''P'''			)
												_UpperCAmelCase						:  Optional[Any]     					=	qtd_bp + 1
								else:
												data_out_gab.append('''D'''			)

								# Sorts the data to the new output size
								if data_out_gab[-1] == "D":
												data_output.append(data[cont_data]			)
								else:
												parity_received.append(data[cont_data]			)
								cont_data += 1

				# -----------calculates the parity with the data
				_UpperCAmelCase						:  Optional[int]     					=	[]
				_UpperCAmelCase						:  List[Any]     					=	[]
				_UpperCAmelCase						:  Optional[Any]     					=	[bin(__A			)[2:] for x in range(1      ,					size_par + len(__A			) + 1			)]

				#  sorted information data for the size of the output data
				_UpperCAmelCase						:  List[Any]     					=	[]
				# Data position feedback + parity
				_UpperCAmelCase						:  int     					=	[]
				# Parity bit counter
				_UpperCAmelCase						:  Dict     					=	0
				# Counter p data bit reading
				_UpperCAmelCase						:  Optional[Any]     					=	0

				for x in range(1      ,					size_par + len(__A			) + 1			):
								# Performs a template position of bits - who should be given,
								# and who should be parity
								if qtd_bp < size_par and (np.log(__A			) / np.log(2			)).is_integer():
												data_out_gab.append('''P'''			)
												_UpperCAmelCase						:  List[Any]     					=	qtd_bp + 1
								else:
												data_out_gab.append('''D'''			)

								# Sorts the data to the new output size
								if data_out_gab[-1] == "D":
												data_ord.append(data_output[cont_data]			)
												cont_data += 1
								else:
												data_ord.append(__A			)

								# Calculates parity
				_UpperCAmelCase						:  Optional[int]     					=	0  # parity bit counter
				for bp in range(1      ,					size_par + 1			):
								# Bit counter one for a certain parity
								_UpperCAmelCase						:  Optional[int]     					=	0
								# Counter to control loop reading
								_UpperCAmelCase						:  Optional[int]     					=	0
								for x in data_ord:
												if x is not None:
																try:
																				_UpperCAmelCase						:  Any     					=	(bin_pos[cont_loop])[-1 * (bp)]
																except IndexError:
																				_UpperCAmelCase						:  str     					=	'''0'''
																if aux == "1" and x == "1":
																				cont_bo += 1
												cont_loop += 1
								parity.append(str(cont_bo % 2			)			)

								qtd_bp += 1

				# Mount the message
				_UpperCAmelCase						:  Dict     					=	0  # Parity bit counter
				for x in range(0      ,					size_par + len(__A			)			):
								if data_ord[x] is None:
												data_out.append(str(parity[cont_bp]			)			)
												cont_bp += 1
								else:
												data_out.append(data_ord[x]			)

				_UpperCAmelCase						:  Union[str, Any]     					=	parity_received == parity
				return data_output, ack



lowerCAmelCase__							=			float("inf")






class     __magic_name__     :


 def __init__(    self		:			List[str]      ,    lowerCAmelCase__		:			Dict     )     ->   List[Any]:
   UpperCAmelCase          =	[0] * n
   UpperCAmelCase          =	[0] * n
   UpperCAmelCase          =	[0] * n
   UpperCAmelCase          =	[[] for _ in range(lowerCAmelCase__     )]


 def _UpperCamelCase						(    self		:			List[Any]      ,    lowerCAmelCase__		:			Tuple      ,    lowerCAmelCase__		:			Dict      ,    lowerCAmelCase__		:			str      ,    lowerCAmelCase__		:			Optional[Any]=0     )     ->   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 _UpperCamelCase						(    self		:			List[str]      ,    lowerCAmelCase__		:			Union[str, Any]      ,    lowerCAmelCase__		:			List[Any]      ,    lowerCAmelCase__		:			Any     )     ->   List[str]:
   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 _UpperCamelCase						(    self		:			str      ,    lowerCAmelCase__		:			str      ,    lowerCAmelCase__		:			Tuple     )     ->   int:
   UpperCAmelCase   ,						UpperCAmelCase          =	0, source
   for l in range(3_1     ):  # 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]) >> (3_0 - 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))



