from __future__ import annotations


def    a__       (						__UpperCamelCase   ,					__UpperCamelCase ):
      print(F'''Vertex\tShortest Distance from vertex {src}''' )
      for i, d in enumerate(__UpperCamelCase ):
            print(F'''{i}\t\t{d}''' )


def    a__       (						__UpperCamelCase   ,					__UpperCamelCase   ,					__UpperCamelCase ):
      for j in range(__UpperCamelCase ):
            SCREAMING_SNAKE_CASE_   ,       SCREAMING_SNAKE_CASE_   ,       SCREAMING_SNAKE_CASE_      =     (graph[j][k] for k in ["src", "dst", "weight"])
            if distance[u] != float("inf" ) and distance[u] + w < distance[v]:
                  return True
      return False


def    a__       (						__UpperCamelCase   ,					__UpperCamelCase   ,					__UpperCamelCase   ,					__UpperCamelCase ):
      SCREAMING_SNAKE_CASE_      =     [float("inf" )] * vertex_count
      SCREAMING_SNAKE_CASE_      =     0.0

      for _ in range(vertex_count - 1 ):
            for j in range(__UpperCamelCase ):
                  SCREAMING_SNAKE_CASE_   ,       SCREAMING_SNAKE_CASE_   ,       SCREAMING_SNAKE_CASE_      =     (graph[j][k] for k in ["src", "dst", "weight"])

                  if distance[u] != float("inf" ) and distance[u] + w < distance[v]:
                        SCREAMING_SNAKE_CASE_      =     distance[u] + w

      SCREAMING_SNAKE_CASE_      =     check_negative_cycle(__UpperCamelCase   ,					__UpperCamelCase   ,					__UpperCamelCase )
      if negative_cycle_exists:
            raise Exception("Negative cycle found" )

      return distance


if __name__ == "__main__":
      import doctest

      doctest.testmod()

      A   :     Any       =				int(input("Enter number of vertices: ").strip())
      A   :     Optional[Any]       =				int(input("Enter number of edges: ").strip())

      A   :     list[dict[str, int]]       =				[{} for _ in range(E)]

      for i in range(E):
            print("Edge ", i + 1)
            A   ,				A   ,				A   :     Dict       =				(
                int(x)
                for x in input("Enter source, destination, weight: ").strip().split(" ")
            )
            A   :     Optional[Any]       =				{"src": src, "dst": dest, "weight": weight}

      A   :     Union[str, Any]       =				int(input("\nEnter shortest path source:").strip())
      A   :     int       =				bellman_ford(graph, V, E, source)
      print_distance(shortest_distance, 0)



def    a__       (						__UpperCamelCase ):
      if not head:
            return True
      # split the list to two parts
      SCREAMING_SNAKE_CASE_   ,       SCREAMING_SNAKE_CASE_      =     head.next, head
      while fast and fast.next:
            SCREAMING_SNAKE_CASE_      =     fast.next.next
            SCREAMING_SNAKE_CASE_      =     slow.next
      SCREAMING_SNAKE_CASE_      =     slow.next
      SCREAMING_SNAKE_CASE_      =     None  # Don't forget here! But forget still works!
      # reverse the second part
      SCREAMING_SNAKE_CASE_      =     None
      while second:
            SCREAMING_SNAKE_CASE_      =     second.next
            SCREAMING_SNAKE_CASE_      =     node
            SCREAMING_SNAKE_CASE_      =     second
            SCREAMING_SNAKE_CASE_      =     nxt
      # compare two parts
      # second part has the same or one less node
      while node:
            if node.val != head.val:
                  return False
            SCREAMING_SNAKE_CASE_      =     node.next
            SCREAMING_SNAKE_CASE_      =     head.next
      return True


def    a__       (						__UpperCamelCase ):
      if not head or not head.next:
            return True

      # 1. Get the midpoint (slow)
      SCREAMING_SNAKE_CASE_      =     SCREAMING_SNAKE_CASE_      =     SCREAMING_SNAKE_CASE_      =     head
      while fast and fast.next:
            SCREAMING_SNAKE_CASE_   ,       SCREAMING_SNAKE_CASE_      =     fast.next.next, slow.next

      # 2. Push the second half into the stack
      SCREAMING_SNAKE_CASE_      =     [slow.val]
      while slow.next:
            SCREAMING_SNAKE_CASE_      =     slow.next
            stack.append(slow.val )

      # 3. Comparison
      while stack:
            if stack.pop() != cur.val:
                  return False
            SCREAMING_SNAKE_CASE_      =     cur.next

      return True





def    a__       (						__UpperCamelCase ):
      if not head or not head.next:
            return True
      SCREAMING_SNAKE_CASE_      =     {}
      SCREAMING_SNAKE_CASE_      =     0
      while head:
            if head.val in d:
                  d[head.val].append(__UpperCamelCase )
            else:
                  SCREAMING_SNAKE_CASE_      =     [pos]
            SCREAMING_SNAKE_CASE_      =     head.next
            pos += 1
      SCREAMING_SNAKE_CASE_      =     pos - 1
      SCREAMING_SNAKE_CASE_      =     0
      for v in d.values():
            if len(__UpperCamelCase ) % 2 != 0:
                  middle += 1
            else:
                  SCREAMING_SNAKE_CASE_      =     0
                  for i in range(0   ,					len(__UpperCamelCase ) ):
                        if v[i] + v[len(__UpperCamelCase ) - 1 - step] != checksum:
                              return False
                        step += 1
            if middle > 1:
                  return False
      return True


