



def     __lowercase(	UpperCAmelCase__ ):


      """simple docstring"""



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

def     __lowercase(	UpperCAmelCase__ ):


      """simple docstring"""



      if not head or not head.next:
            return True

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

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

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

      return True






def     __lowercase(	UpperCAmelCase__ ):


      """simple docstring"""



      if not head or not head.next:
            return True
      lowerCamelCase								=		{}
      lowerCamelCase								=		0
      while head:
            if head.val in d:
                  d[head.val].append(UpperCAmelCase__ )
            else:
                  lowerCamelCase								=		[pos]
            lowerCamelCase								=		head.next
            pos += 1
      lowerCamelCase								=		pos - 1
      lowerCamelCase								=		0
      for v in d.values():
            if len(UpperCAmelCase__ ) % 2 != 0:
                  middle += 1
            else:
                  lowerCamelCase								=		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




from __future__ import annotations

from collections import deque
from collections.abc import Iterator
from dataclasses import dataclass





@dataclass
class    lowerCamelCase__  :
     """simple docstring"""



     _A       =			42
     _A       =			42





class    lowerCamelCase__  :
     """simple docstring"""



     def __init__(self				,			__a    ):






           '''simple docstring'''



           lowerCamelCase								=		[[] for _ in range(__a    )]
           lowerCamelCase								=		size







     def __getitem__(self				,			__a    ):






           '''simple docstring'''



           return iter(self._graph[vertex]    )







     @property
     def 						_a      (self    ):






           '''simple docstring'''



           return self._size







     def 						_a      (self				,			__a				,			__a				,			__a    ):






           '''simple docstring'''



           if weight not in (0, 1):
                 raise ValueError("Edge weight must be either 0 or 1."    )

           if to_vertex < 0 or to_vertex >= self.size:
                 raise ValueError("Vertex indexes must be in [0; size)."    )

           self._graph[from_vertex].append(Edge(__a				,			__a    )    )







     def 						_a      (self				,			__a				,			__a    ):






           '''simple docstring'''



           lowerCamelCase								=		deque([start_vertex]    )
           lowerCamelCase								=		[None] * self.size
           lowerCamelCase								=		0

           while queue:
                 lowerCamelCase								=		queue.popleft()
                 lowerCamelCase								=		distances[current_vertex]
                 if current_distance is None:
                       continue

                 for edge in self[current_vertex]:
                       lowerCamelCase								=		current_distance + edge.weight
                       lowerCamelCase								=		distances[edge.destination_vertex]
                       if (
                           isinstance(__a				,			__a    )
                           and new_distance >= dest_vertex_distance
                       ):
                             continue
                       lowerCamelCase								=		new_distance
                       if edge.weight == 0:
                             queue.appendleft(edge.destination_vertex    )
                       else:
                             queue.append(edge.destination_vertex    )

           if distances[finish_vertex] is None:
                 raise ValueError("No path from start_vertex to finish_vertex."    )

           return distances[finish_vertex]


if __name__ == "__main__":
     import doctest

     doctest.testmod()