





'''simple docstring'''





from __future__ import annotations

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



@dataclass
class 							_UpperCamelCase					:
       _UpperCamelCase				:					int
       _UpperCamelCase				:					int



class 							_UpperCamelCase					:

       def __init__(		self: Optional[Any]					,   _SCREAMING_SNAKE_CASE: int		)       -> Any:




              """simple docstring"""


              UpperCamelCase_          =  [[] for _ in range(_SCREAMING_SNAKE_CASE		)]
              UpperCamelCase_          =  size

       def __getitem__(		self: List[str]					,   _SCREAMING_SNAKE_CASE: int		)       -> Iterator[Edge]:




              """simple docstring"""


              return iter(self._graph[vertex]		)

       @property
       def lowercase (		self: Dict		)       -> List[str]:




              """simple docstring"""


              return self._size

       def lowercase (		self: Union[str, Any]					,   _SCREAMING_SNAKE_CASE: int					,   _SCREAMING_SNAKE_CASE: int					,   _SCREAMING_SNAKE_CASE: int		)       -> List[str]:




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



       def lowercase (		self: Any					,   _SCREAMING_SNAKE_CASE: int					,   _SCREAMING_SNAKE_CASE: int		)       -> int | None:




              """simple docstring"""


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

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

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








_UpperCAmelCase        =				{
    'a': 'AAAAA',
    'b': 'AAAAB',
    'c': 'AAABA',
    'd': 'AAABB',
    'e': 'AABAA',
    'f': 'AABAB',
    'g': 'AABBA',
    'h': 'AABBB',
    'i': 'ABAAA',
    'j': 'BBBAA',
    'k': 'ABAAB',
    'l': 'ABABA',
    'm': 'ABABB',
    'n': 'ABBAA',
    'o': 'ABBAB',
    'p': 'ABBBA',
    'q': 'ABBBB',
    'r': 'BAAAA',
    's': 'BAAAB',
    't': 'BAABA',
    'u': 'BAABB',
    'v': 'BBBAB',
    'w': 'BABAA',
    'x': 'BABAB',
    'y': 'BABBA',
    'z': 'BABBB',
    ' ': ' ',
}


_UpperCAmelCase        =				{value: key for key, value in encode_dict.items()}




def  lowerCAmelCase_ (							UpperCamelCase_  )     ->		str:
       UpperCamelCase_          =  ""
       for letter in word.lower():
              if letter.isalpha() or letter == " ":
                     encoded += encode_dict[letter]
              else:
                     raise Exception("encode() accepts only letters of the alphabet and spaces"  )
       return encoded




def  lowerCAmelCase_ (							UpperCamelCase_  )     ->		str:
       if set(UpperCamelCase_  ) - {"A", "B", " "} != set():
              raise Exception("decode() accepts only 'A', 'B' and spaces"  )
       UpperCamelCase_          =  ""
       for word in coded.split():
              while len(UpperCamelCase_  ) != 0:
                     decoded += decode_dict[word[:5]]
                     UpperCamelCase_          =  word[5:]
              decoded += " "
       return decoded.strip()


if __name__ == "__main__":
     from doctest import testmod

     testmod()

