






from __future__ import annotations

lowerCamelCase      :       List[str]    =						{
    '''A''': ['''B''', '''C''', '''E'''],
    '''B''': ['''A''', '''D''', '''E'''],
    '''C''': ['''A''', '''F''', '''G'''],
    '''D''': ['''B'''],
    '''E''': ['''A''', '''B''', '''D'''],
    '''F''': ['''C'''],
    '''G''': ['''C'''],
}



class 				_UpperCamelCase      :


      def __init__(						self       ,    __UpperCamelCase       ,    __UpperCamelCase						)->						None:
           __lowerCAmelCase             =       graph
           # mapping node to its parent in resulting breadth first tree
           __lowerCAmelCase             =       {}
           __lowerCAmelCase             =       source_vertex


      def 			__UpperCAmelCase		(						self						)->						None:
           __lowerCAmelCase             =       {self.source_vertex}
           __lowerCAmelCase             =       None
           __lowerCAmelCase             =       [self.source_vertex]  # first in first out queue

           while queue:
                __lowerCAmelCase             =       queue.pop(0						)
                for adjacent_vertex in self.graph[vertex]:
                     if adjacent_vertex not in visited:
                          visited.add(__UpperCamelCase						)
                          __lowerCAmelCase             =       vertex
                          queue.append(__UpperCamelCase						)


      def 			__UpperCAmelCase		(						self       ,    __UpperCamelCase						)->						str:
           if target_vertex == self.source_vertex:
                return self.source_vertex

           __lowerCAmelCase             =       self.parent.get(__UpperCamelCase						)
           if target_vertex_parent is None:
                __lowerCAmelCase             =       (
                    F"""No path from vertex: {self.source_vertex} to vertex: {target_vertex}"""
                )
                raise ValueError(__UpperCamelCase						)

           return self.shortest_path(__UpperCamelCase						) + F"""->{target_vertex}"""


if __name__ == "__main__":
 lowerCamelCase      :       int    =						Graph(graph, '''G''')
 g.breath_first_search()
 print(g.shortest_path('''D'''))
 print(g.shortest_path('''G'''))
 print(g.shortest_path('''Foo'''))














import os

# Precomputes a list of the 100 first triangular numbers
lowerCamelCase      :       str    =						[int(0.5 * n * (n + 1)) for n in range(1, 101)]





def    __lowerCAmelCase   (    ):
     __lowerCAmelCase             =       os.path.dirname(os.path.realpath(__snake_case							)							)
     __lowerCAmelCase             =       os.path.join(__snake_case       ,			"words.txt"							)

     __lowerCAmelCase             =       ""
     with open(__snake_case							) as f:
          __lowerCAmelCase             =       f.readline()

     __lowerCAmelCase             =       [word.strip("\""							) for word in words.strip("\r\n"							).split(","							)]
     __lowerCAmelCase             =       [
         word
         for word in [sum(ord(__snake_case							) - 64 for x in word							) for word in words]
         if word in TRIANGULAR_NUMBERS
     ]
     return len(__snake_case							)


if __name__ == "__main__":
 print(solution())






