



from __future__ import annotations

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


@dataclass
class 						lowercase    :
						'''simple docstring'''


						UpperCAmelCase			:		int
						UpperCAmelCase			:		int


class 						lowercase    :
						'''simple docstring'''


						def __init__(  self    :				List[Any]       ,	snake_case    :				int	):



											'''simple docstring'''


											SCREAMING_SNAKE_CASE							:     list[list[Edge]]						=				[[] for _ in range(snake_case	)]
											SCREAMING_SNAKE_CASE							:     str						=				size







						def __getitem__(  self    :				str       ,	snake_case    :				int	):



											'''simple docstring'''


											return iter(self._graph[vertex]	)







						@property
						def       lowerCamelCase_				(  self    :				Optional[Any]	):



											'''simple docstring'''


											return self._size







						def       lowerCamelCase_				(  self    :				str       ,	snake_case    :				int       ,	snake_case    :				int       ,	snake_case    :				int	):



											'''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       lowerCamelCase_				(  self    :				Optional[Any]       ,	snake_case    :				int       ,	snake_case    :				int	):



											'''simple docstring'''


											SCREAMING_SNAKE_CASE							:     Optional[Any]						=				deque([start_vertex]	)
											SCREAMING_SNAKE_CASE							:     list[int | None]						=				[None] * self.size
											SCREAMING_SNAKE_CASE							:     str						=				0

											while queue:
																SCREAMING_SNAKE_CASE							:     Dict						=				queue.popleft()
																SCREAMING_SNAKE_CASE							:     Optional[int]						=				distances[current_vertex]
																if current_distance is None:
																					continue

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




def        __a			(   __lowerCAmelCase      ,	__lowerCAmelCase = 0   )     ->     list:
					SCREAMING_SNAKE_CASE							:     int						=				length or len(__lowerCAmelCase   )
					SCREAMING_SNAKE_CASE							:     Union[str, Any]						=				False
					for i in range(length - 1   ):
										if list_data[i] > list_data[i + 1]:
															SCREAMING_SNAKE_CASE					,  SCREAMING_SNAKE_CASE							:     List[Any]						=				list_data[i + 1], list_data[i]
															SCREAMING_SNAKE_CASE							:     Any						=				True

					return list_data if not swapped else bubble_sort(__lowerCAmelCase      ,	length - 1   )


if __name__ == "__main__":
			import doctest

			doctest.testmod()