


'''simple docstring'''

from __future__ import annotations







class 			UpperCAmelCase			:

 def __init__(			self			:						List[str],       a_			:						int       ):





    """simple docstring"""



    UpperCamelCase__			    =    vertices
    UpperCamelCase__			    =    [[0] * vertices for _ in range(a_       )]

 def 		lowercase_    (			self			:						List[Any],       a_			:						list[int]       ):





    """simple docstring"""



    print("Vertex \t Distance from Source"       )
    for vertex in range(self.vertices       ):
       print(a_,       "\t\t",       distances_from_source[vertex]       )

 def 		lowercase_    (			self			:						List[Any],       a_			:						list[int],       a_			:						list[bool]       ):





    """simple docstring"""



    UpperCamelCase__			    =    1e7
    UpperCamelCase__			    =    0

    # Search not nearest vertex not in the shortest path tree
    for vertex in range(self.vertices       ):
       if distances_from_source[vertex] < minimum and visited[vertex] is False:
          UpperCamelCase__			    =    distances_from_source[vertex]
          UpperCamelCase__			    =    vertex
    return min_index

 def 		lowercase_    (			self			:						Optional[int],       a_			:						int       ):





    """simple docstring"""



    UpperCamelCase__			    =    [int(1e7       )] * self.vertices  # distances from the source
    UpperCamelCase__			    =    0
    UpperCamelCase__			    =    [False] * self.vertices

    for _ in range(self.vertices       ):
       UpperCamelCase__			    =    self.minimum_distance(a_,       a_       )
       UpperCamelCase__			    =    True

       # Update dist value of the adjacent vertices
       # of the picked vertex only if the current
       # distance is greater than new distance and
       # the vertex in not in the shortest path tree
       for v in range(self.vertices       ):
          if (
              self.graph[u][v] > 0
              and visited[v] is False
              and distances[v] > distances[u] + self.graph[u][v]
          ):
             UpperCamelCase__			    =    distances[u] + self.graph[u][v]

    self.print_solution(a_       )


if __name__ == "__main__":
       __lowercase:		Dict    						=  Graph(9)
       __lowercase:		List[str]    						=  [
           [0, 4, 0, 0, 0, 0, 0, 8, 0],
           [4, 0, 8, 0, 0, 0, 0, 11, 0],
           [0, 8, 0, 7, 0, 4, 0, 0, 2],
           [0, 0, 7, 0, 9, 14, 0, 0, 0],
           [0, 0, 0, 9, 0, 10, 0, 0, 0],
           [0, 0, 4, 14, 10, 0, 2, 0, 0],
           [0, 0, 0, 0, 0, 2, 0, 1, 6],
           [8, 11, 0, 0, 0, 0, 1, 0, 7],
           [0, 0, 2, 0, 0, 0, 6, 7, 0],
       ]
       graph.dijkstra(0)



'''simple docstring'''

from __future__ import annotations



def 							SCREAMING_SNAKE_CASE__(		_UpperCamelCase   :					list[list[int]]     ,		_UpperCamelCase   :					list[list[int]] )		->       list[int]:





   '''simple docstring'''







   assert len(_UpperCamelCase ) == len(_UpperCamelCase )

   UpperCamelCase__			    =    len(_UpperCamelCase )
   UpperCamelCase__			    =    list(range(_UpperCamelCase ) )
   UpperCamelCase__			    =    [-1] * n  # who the donor has donated to
   UpperCamelCase__			    =    [-1] * n  # who the recipient has received from
   UpperCamelCase__			    =    [0] * n

   while unmatched_donors:
      UpperCamelCase__			    =    unmatched_donors[0]
      UpperCamelCase__			    =    donor_pref[donor]
      UpperCamelCase__			    =    donor_preference[num_donations[donor]]
      num_donations[donor] += 1
      UpperCamelCase__			    =    recipient_pref[recipient]
      UpperCamelCase__			    =    rec_record[recipient]

      if prev_donor != -1:
         if rec_preference.index(_UpperCamelCase ) > rec_preference.index(_UpperCamelCase ):
            UpperCamelCase__			    =    donor
            UpperCamelCase__			    =    recipient
            unmatched_donors.append(_UpperCamelCase )
            unmatched_donors.remove(_UpperCamelCase )
      else:
         UpperCamelCase__			    =    donor
         UpperCamelCase__			    =    recipient
         unmatched_donors.remove(_UpperCamelCase )
   return donor_record