





from __future__ import annotations

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





@dataclass
class UpperCAmelCase_				:
  __lowerCAmelCase   :						int
  __lowerCAmelCase   :						int





class UpperCAmelCase_				:


  def __init__(							self ,__snake_case ):



       """simple docstring"""





       A_          =       [[] for _ in range(__snake_case )]
       A_          =       size


  def __getitem__(							self ,__snake_case ):



       """simple docstring"""





       return iter(self._graph[vertex] )


  @property
  def 						__UpperCAmelCase     (							self ):



       """simple docstring"""





       return self._size


  def 						__UpperCAmelCase     (							self ,__snake_case ,__snake_case ,__snake_case ):



       """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(__snake_case ,__snake_case ) )




  def 						__UpperCAmelCase     (							self ,__snake_case ,__snake_case ):



       """simple docstring"""





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

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

            for edge in self[current_vertex]:
                 A_          =       current_distance + edge.weight
                 A_          =       distances[edge.destination_vertex]
                 if (
                     isinstance(__snake_case ,__snake_case )
                     and new_distance >= dest_vertex_distance
                 ):
                      continue
                 A_          =       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()










# Author: OMKAR PATHAK, Nwachukwu Chidiebere

# Use a Python dictionary to construct the graph.
from __future__ import annotations

from pprint import pformat
from typing import Generic, TypeVar

a__      :     Optional[int]         =		TypeVar('T')





class UpperCAmelCase_				( Generic[T] ):


  def __init__(							self ,__snake_case = True ):



       """simple docstring"""





       A_          =       {}  # dictionary of lists
       A_          =       directed


  def 						__UpperCAmelCase     (							self ,__snake_case ,__snake_case ):



       """simple docstring"""





       if not self.directed:  # For undirected graphs
            # if both source vertex and destination vertex are both present in the
            # adjacency list, add destination vertex to source vertex list of adjacent
            # vertices and add source vertex to destination vertex list of adjacent
            # vertices.
            if source_vertex in self.adj_list and destination_vertex in self.adj_list:
                 self.adj_list[source_vertex].append(__snake_case )
                 self.adj_list[destination_vertex].append(__snake_case )
            # if only source vertex is present in adjacency list, add destination vertex
            # to source vertex list of adjacent vertices, then create a new vertex with
            # destination vertex as key and assign a list containing the source vertex
            # as it's first adjacent vertex.
            elif source_vertex in self.adj_list:
                 self.adj_list[source_vertex].append(__snake_case )
                 A_          =       [source_vertex]
            # if only destination vertex is present in adjacency list, add source vertex
            # to destination vertex list of adjacent vertices, then create a new vertex
            # with source vertex as key and assign a list containing the source vertex
            # as it's first adjacent vertex.
            elif destination_vertex in self.adj_list:
                 self.adj_list[destination_vertex].append(__snake_case )
                 A_          =       [destination_vertex]
            # if both source vertex and destination vertex are not present in adjacency
            # list, create a new vertex with source vertex as key and assign a list
            # containing the destination vertex as it's first adjacent vertex also
            # create a new vertex with destination vertex as key and assign a list
            # containing the source vertex as it's first adjacent vertex.
            else:
                 A_          =       [destination_vertex]
                 A_          =       [source_vertex]
       else:  # For directed graphs
            # if both source vertex and destination vertex are present in adjacency
            # list, add destination vertex to source vertex list of adjacent vertices.
            if source_vertex in self.adj_list and destination_vertex in self.adj_list:
                 self.adj_list[source_vertex].append(__snake_case )
            # if only source vertex is present in adjacency list, add destination
            # vertex to source vertex list of adjacent vertices and create a new vertex
            # with destination vertex as key, which has no adjacent vertex
            elif source_vertex in self.adj_list:
                 self.adj_list[source_vertex].append(__snake_case )
                 A_          =       []
            # if only destination vertex is present in adjacency list, create a new
            # vertex with source vertex as key and assign a list containing destination
            # vertex as first adjacent vertex
            elif destination_vertex in self.adj_list:
                 A_          =       [destination_vertex]
            # if both source vertex and destination vertex are not present in adjacency
            # list, create a new vertex with source vertex as key and a list containing
            # destination vertex as it's first adjacent vertex. Then create a new vertex
            # with destination vertex as key, which has no adjacent vertex
            else:
                 A_          =       [destination_vertex]
                 A_          =       []

       return self




  def __repr__(							self ):



       """simple docstring"""





       return pformat(self.adj_list )



