



"""simple docstring"""





import math
class    lowercase__     :







       '''simple docstring'''


       def __init__(							self    :						Optional[Any]	,       _UpperCAmelCase    :						List[str]=0					)				->		List[str]:  # a graph with Node 0,1,...,N-1


             '''simple docstring'''




             UpperCAmelCase_    				=							n
             UpperCAmelCase_    				=							[
                 [math.inf for j in range(0	,       __UpperCamelCase					)] for i in range(0	,       __UpperCamelCase					)
             ]  # adjacency matrix for weight
             UpperCAmelCase_    				=							[
                 [math.inf for j in range(0	,       __UpperCamelCase					)] for i in range(0	,       __UpperCamelCase					)
             ]  # dp[i][j] stores minimum distance from i to j



       def   lowercase__       (							self    :						Union[str, Any]	,       _UpperCAmelCase    :						int	,       _UpperCAmelCase    :						Union[str, Any]	,       _UpperCAmelCase    :						List[str]					)				->		str:


             '''simple docstring'''




             UpperCAmelCase_    				=							w



       def   lowercase__       (							self    :						Optional[int]					)				->		List[Any]:


             '''simple docstring'''




             for k in range(0	,       self.n					):
                   for i in range(0	,       self.n					):
                         for j in range(0	,       self.n					):
                               UpperCAmelCase_    				=							min(self.dp[i][j]	,       self.dp[i][k] + self.dp[k][j]					)







       def   lowercase__       (							self    :						Optional[Any]	,       _UpperCAmelCase    :						str	,       _UpperCAmelCase    :						Optional[int]					)				->		Dict:


             '''simple docstring'''




             return self.dp[u][v]


if __name__ == "__main__":
  lowerCamelCase            =		Graph(5)
  graph.add_edge(0, 2, 9)
  graph.add_edge(0, 4, 10)
  graph.add_edge(1, 3, 5)
  graph.add_edge(2, 3, 7)
  graph.add_edge(3, 0, 10)
  graph.add_edge(3, 1, 2)
  graph.add_edge(3, 2, 1)
  graph.add_edge(3, 4, 6)
  graph.add_edge(4, 1, 3)
  graph.add_edge(4, 2, 4)
  graph.add_edge(4, 3, 9)
  graph.floyd_warshall()
  graph.show_min(1, 4)
  graph.show_min(0, 3)









"""simple docstring"""





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

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

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

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

      return True


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




