
"""simple docstring"""
from collections import deque





def    _lowerCAmelCase    (     lowerCamelCase__							:							Tuple				)  ->    str:
  _SCREAMING_SNAKE_CASE   :				int							    = len(lowerCamelCase_				)
  _SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = deque()
  _SCREAMING_SNAKE_CASE   :				Tuple							    = [False for _ in range(lowerCamelCase_				)]
  _SCREAMING_SNAKE_CASE   :				Optional[int]							    = [-1 for _ in range(lowerCamelCase_				)]
  _SCREAMING_SNAKE_CASE   :				Dict							    = index_of[:]

  def strong_connect(lowerCamelCase__							:							Union[str, Any],						lowerCamelCase__							:							Optional[Any],						lowerCamelCase__							:							Optional[int]				):
    _SCREAMING_SNAKE_CASE   :				Any							    = index  # the number when this node is seen
    _SCREAMING_SNAKE_CASE   :				Any							    = index  # lowest rank node reachable from here
    index += 1
    stack.append(lowerCamelCase_				)
    _SCREAMING_SNAKE_CASE   :				Optional[Any]							    = True

    for w in g[v]:
      if index_of[w] == -1:
        _SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = strong_connect(lowerCamelCase_,						lowerCamelCase_,						lowerCamelCase_				)
        _SCREAMING_SNAKE_CASE   :				Any							    = (
            lowlink_of[w] if lowlink_of[w] < lowlink_of[v] else lowlink_of[v]
        )
      elif on_stack[w]:
        _SCREAMING_SNAKE_CASE   :				List[Any]							    = (
            lowlink_of[w] if lowlink_of[w] < lowlink_of[v] else lowlink_of[v]
        )

    if lowlink_of[v] == index_of[v]:
      _SCREAMING_SNAKE_CASE   :				Any							    = []
      _SCREAMING_SNAKE_CASE   :				str							    = stack.pop()
      _SCREAMING_SNAKE_CASE   :				List[str]							    = False
      component.append(lowerCamelCase_				)
      while w != v:
        _SCREAMING_SNAKE_CASE   :				Any							    = stack.pop()
        _SCREAMING_SNAKE_CASE   :				Dict							    = False
        component.append(lowerCamelCase_				)
      components.append(lowerCamelCase_				)
    return index

  _SCREAMING_SNAKE_CASE   :				List[Any]							    = []
  for v in range(lowerCamelCase_				):
    if index_of[v] == -1:
      strong_connect(lowerCamelCase_,						0,						lowerCamelCase_				)

  return components





def    _lowerCAmelCase    (     lowerCamelCase__							:							Any,						lowerCamelCase__							:							Tuple				)  ->    Any:
  _SCREAMING_SNAKE_CASE   :				Tuple							    = [[] for _ in range(lowerCamelCase_				)]
  for u, v in edges:
    g[u].append(lowerCamelCase_				)
  return g


if __name__ == "__main__":
    # Test
    lowercase_       :						Any     					=	7
    lowercase_       :						Optional[Any]     					=	[0, 0, 1, 2, 3, 3, 4, 4, 6]
    lowercase_       :						str     					=	[1, 3, 2, 0, 1, 4, 5, 6, 5]
    lowercase_       :						str     					=	[(u, v) for u, v in zip(source, target)]
    lowercase_       :						Optional[int]     					=	create_graph(n_vertices, edges)

    assert [[5], [6], [4], [3, 2, 1, 0]] == tarjan(g)





"""simple docstring"""
def    _lowerCAmelCase    (     lowerCamelCase__							:							str,						lowerCamelCase__							:							str				)  ->    Union[str, Any]:
  print("\nThe shortest path matrix using Floyd Warshall algorithm\n"				)
  for i in range(lowerCamelCase__				):
    for j in range(lowerCamelCase__				):
      if dist[i][j] != float("inf"				):
        print(int(dist[i][j]				),						end="\t"				)
      else:
        print("INF",						end="\t"				)
    print()





def    _lowerCAmelCase    (     lowerCamelCase__							:							Dict,						lowerCamelCase__							:							Any				)  ->    List[str]:
  _SCREAMING_SNAKE_CASE   :				List[Any]							    = [[float("inf"				) for _ in range(lowerCamelCase__				)] for _ in range(lowerCamelCase__				)]

  for i in range(lowerCamelCase__				):
    for j in range(lowerCamelCase__				):
      _SCREAMING_SNAKE_CASE   :				List[Any]							    = graph[i][j]

      # check vertex k against all other vertices (i, j)
  for k in range(lowerCamelCase__				):
    # looping through rows of graph array
    for i in range(lowerCamelCase__				):
      # looping through columns of graph array
      for j in range(lowerCamelCase__				):
        if (
            dist[i][k] != float("inf"				)
            and dist[k][j] != float("inf"				)
            and dist[i][k] + dist[k][j] < dist[i][j]
        ):
          _SCREAMING_SNAKE_CASE   :				List[Any]							    = dist[i][k] + dist[k][j]

  _print_dist(lowerCamelCase__,						lowerCamelCase__				)
  return dist, v


if __name__ == "__main__":
      lowercase_       :						Tuple     					=	int(input('''Enter number of vertices: '''))
      lowercase_       :						List[Any]     					=	int(input('''Enter number of edges: '''))

      lowercase_       :						Optional[Any]     					=	[[float('''inf''') for i in range(v)] for j in range(v)]

      for i in range(v):
            lowercase_       :						Tuple     					=	0.0

            # src and dst are indices that must be within the array size graph[e][v]
            # failure to follow this will result in an error
      for i in range(e):
            print('''\nEdge ''', i + 1)
            lowercase_       :						str     					=	int(input('''Enter source:'''))
            lowercase_       :						Optional[Any]     					=	int(input('''Enter destination:'''))
            lowercase_       :						Union[str, Any]     					=	float(input('''Enter weight:'''))
            lowercase_       :						str     					=	weight

      floyd_warshall(graph, v)

      # Example Input
      # Enter number of vertices: 3
      # Enter number of edges: 2

      # # generated graph from vertex and edge inputs
      # [[inf, inf, inf], [inf, inf, inf], [inf, inf, inf]]
      # [[0.0, inf, inf], [inf, 0.0, inf], [inf, inf, 0.0]]

      # specify source, destination and weight for edge #1
      # Edge  1
      # Enter source:1
      # Enter destination:2
      # Enter weight:2

      # specify source, destination and weight for edge #2
      # Edge  2
      # Enter source:2
      # Enter destination:1
      # Enter weight:1

      # # Expected Output from the vertice, edge and src, dst, weight inputs!!
      # 0		INF	INF
      # INF	0	2
      # INF	1	0



