


__a	 =      {
    """A""": ["""B""", """C""", """E"""],
    """B""": ["""A""", """D""", """E"""],
    """C""": ["""A""", """F""", """G"""],
    """D""": ["""B"""],
    """E""": ["""A""", """B""", """D"""],
    """F""": ["""C"""],
    """G""": ["""C"""],
}
def 	_UpperCamelCase					(    lowerCAmelCase_	,    lowerCAmelCase_	,    lowerCAmelCase_ )    ->list[str]:
   UpperCAmelCase      					=  set()
   # keep track of all the paths to be checked
   UpperCAmelCase      					=  [[start]]

   # return path if start is goal
   if start == goal:
      return [start]

   # keeps looping until all possible paths have been checked
   while queue:
      # pop the first path from the queue
      UpperCAmelCase      					=  queue.pop(0 )
      # get the last node from the path
      UpperCAmelCase      					=  path[-1]
      if node not in explored:
         UpperCAmelCase      					=  graph[node]
         # go through all neighbour nodes, construct a new path and
         # push it into the queue
         for neighbour in neighbours:
            UpperCAmelCase      					=  list(lowerCAmelCase_ )
            new_path.append(lowerCAmelCase_ )
            queue.append(lowerCAmelCase_ )
            # return path if neighbour is goal
            if neighbour == goal:
               return new_path

            # mark node as explored
         explored.add(lowerCAmelCase_ )

    # in case there's no path between the 2 nodes
   return []
def 	_UpperCamelCase					(    lowerCAmelCase_	,    lowerCAmelCase_	,    lowerCAmelCase_ )    ->int:
   if not graph or start not in graph or target not in graph:
      return -1
   if start == target:
      return 0
   UpperCAmelCase      					=  [start]
   UpperCAmelCase      					=  set(lowerCAmelCase_ )
   # Keep tab on distances from `start` node.
   UpperCAmelCase      					=  {start: 0, target: -1}
   while queue:
      UpperCAmelCase      					=  queue.pop(0 )
      if node == target:
         UpperCAmelCase      					=  (
             dist[node] if dist[target] == -1 else min(dist[target]	,    dist[node] )
         )
      for adjacent in graph[node]:
         if adjacent not in visited:
            visited.add(lowerCAmelCase_ )
            queue.append(lowerCAmelCase_ )
            UpperCAmelCase      					=  dist[node] + 1
   return dist[target]


if __name__ == "__main__":
 print(bfs_shortest_path(demo_graph, """G""", """D"""))  # returns ['G', 'C', 'A', 'B', 'D']
 print(bfs_shortest_path_distance(demo_graph, """G""", """D"""))  # returns 4







def 	_UpperCamelCase					(    lowerCAmelCase_ )    ->Any:
   UpperCAmelCase      					=  0
   UpperCAmelCase      					=  len(lowerCAmelCase_ )

   for i in range(n - 1 ):
      for j in range(i + 1	,    lowerCAmelCase_ ):
         if arr[i] > arr[j]:
            num_inversions += 1

   return num_inversions
def 	_UpperCamelCase					(    lowerCAmelCase_ )    ->Any:
   if len(lowerCAmelCase_ ) <= 1:
      return arr, 0
   UpperCAmelCase      					=  len(lowerCAmelCase_ ) // 2
   UpperCAmelCase      					=  arr[0:mid]
   UpperCAmelCase      					=  arr[mid:]

   UpperCAmelCase					,	UpperCAmelCase      					=  count_inversions_recursive(lowerCAmelCase_ )
   UpperCAmelCase					,	UpperCAmelCase      					=  count_inversions_recursive(lowerCAmelCase_ )
   UpperCAmelCase					,	UpperCAmelCase      					=  _count_cross_inversions(lowerCAmelCase_	,    lowerCAmelCase_ )

   UpperCAmelCase      					=  inversion_p + inversions_q + cross_inversions
   return c, num_inversions
def 	_UpperCamelCase					(    lowerCAmelCase_	,    lowerCAmelCase_ )    ->int:
   UpperCAmelCase      					=  []
   UpperCAmelCase      					=  UpperCAmelCase      					=  UpperCAmelCase      					=  0
   while i < len(lowerCAmelCase_ ) and j < len(lowerCAmelCase_ ):
      if p[i] > q[j]:
         # if P[1] > Q[j], then P[k] > Q[k] for all  i < k <= len(P)
         # These are all inversions. The claim emerges from the
         # property that P is sorted.
         num_inversion += len(lowerCAmelCase_ ) - i
         r.append(q[j] )
         j += 1
      else:
         r.append(p[i] )
         i += 1

   if i < len(lowerCAmelCase_ ):
      r.extend(p[i:] )
   else:
      r.extend(q[j:] )

   return r, num_inversion
def 	_UpperCamelCase					(    )    ->int:
   UpperCAmelCase      					=  [1_0, 2, 1, 5, 5, 2, 1_1]

   # this arr has 8 inversions:
   # (10, 2), (10, 1), (10, 5), (10, 5), (10, 2), (2, 1), (5, 2), (5, 2)

   UpperCAmelCase      					=  count_inversions_bf(lowerCAmelCase_ )
   UpperCAmelCase					,	UpperCAmelCase      					=  count_inversions_recursive(lowerCAmelCase_ )

   assert num_inversions_bf == num_inversions_recursive == 8

   print("""number of inversions = """	,    lowerCAmelCase_ )

   # testing an array with zero inversion (a sorted arr_1)

   arr_a.sort()
   UpperCAmelCase      					=  count_inversions_bf(lowerCAmelCase_ )
   UpperCAmelCase					,	UpperCAmelCase      					=  count_inversions_recursive(lowerCAmelCase_ )

   assert num_inversions_bf == num_inversions_recursive == 0
   print("""number of inversions = """	,    lowerCAmelCase_ )

   # an empty list should also have zero inversions
   UpperCAmelCase      					=  []
   UpperCAmelCase      					=  count_inversions_bf(lowerCAmelCase_ )
   UpperCAmelCase					,	UpperCAmelCase      					=  count_inversions_recursive(lowerCAmelCase_ )

   assert num_inversions_bf == num_inversions_recursive == 0
   print("""number of inversions = """	,    lowerCAmelCase_ )


if __name__ == "__main__":
 main()



