





"""simple docstring"""



a_				=    float("""inf""")






class 	__snake_case      :





 """simple docstring"""


 def __init__(					self      ,		__lowerCamelCase						):



     '''simple docstring'''




     __A					:		List[str]						=  [0] * n
     __A					:		List[Any]						=  [0] * n
     __A					:		List[Any]						=  [0] * n
     __A					:		Any						=  [[] for _ in range(__lowerCamelCase						)]

 def       UpperCamelCase__(					self      ,		__lowerCamelCase      ,		__lowerCamelCase      ,		__lowerCamelCase      ,		__lowerCamelCase=0						):



     '''simple docstring'''




     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      ,		__lowerCamelCase      ,		__lowerCamelCase      ,		__lowerCamelCase						):



     '''simple docstring'''




     if vertex == sink or not flow:
         return flow

     for i in range(self.ptr[vertex]      ,		len(self.adj[vertex]						)						):
         __A					:		str						=  self.adj[vertex][i]
         if self.lvl[e[0]] == self.lvl[vertex] + 1:
             __A					:		Dict						=  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
         __A					:		str						=  self.ptr[vertex] + 1
     return 0







 def       UpperCamelCase__(					self      ,		__lowerCamelCase      ,		__lowerCamelCase						):



     '''simple docstring'''




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

             __A					:		int						=  self.depth_first_search(__lowerCamelCase      ,		__lowerCamelCase      ,		__lowerCamelCase						)
             while p:
                 flow += p
                 __A					:		Optional[Any]						=  self.depth_first_search(__lowerCamelCase      ,		__lowerCamelCase      ,		__lowerCamelCase						)

             if not self.lvl[sink]:
                 break

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



from __future__ import annotations

import sys







def 	__lowercase  (     snake_case_						:						int       ,snake_case_						:						int		)     ->tuple[int, int]:



    '''simple docstring'''







    if abs(snake_case_		) == 1:
        return a, 0
    elif abs(snake_case_		) == 1:
        return 0, b

    __A				, __A					:		int						=  a, b
    __A				, __A					:		Any						=  1, 0
    __A				, __A					:		int						=  0, 1

    while remainder != 0:
        __A					:		List[Any]						=  old_remainder // remainder
        __A				, __A					:		int						=  remainder, old_remainder - quotient * remainder
        __A				, __A					:		List[Any]						=  coeff_a, old_coeff_a - quotient * coeff_a
        __A				, __A					:		Union[str, Any]						=  coeff_b, old_coeff_b - quotient * coeff_b

    # sign correction for negative numbers
    if a < 0:
        __A					:		Optional[Any]						=  -old_coeff_a
    if b < 0:
        __A					:		List[Any]						=  -old_coeff_b

    return old_coeff_a, old_coeff_b







def 	__lowercase  (     )     ->List[str]:



    '''simple docstring'''







    if len(sys.argv		) < 3:
        print('''2 integer arguments required'''		)
        return 1
    __A					:		Optional[int]						=  int(sys.argv[1]		)
    __A					:		Tuple						=  int(sys.argv[2]		)
    print(extended_euclidean_algorithm(snake_case_       ,snake_case_		)		)
    return 0


if __name__ == "__main__":
       raise SystemExit(main())




