


from collections import deque
from math import floor
from random import random
from time import time

class        a	:




							"""simple docstring"""


							def __init__(							self :						str       )			->					Optional[Any]:
														__snake_case	:    Union[str, Any]											=     {}

							def 					__snake_case      (							self :						List[Any]					,			lowerCamelCase :						Union[str, Any]					,			lowerCamelCase :						List[Any]					,			lowerCamelCase :						Tuple=1       )			->					str:






														if self.graph.get(lowerCamelCase__       ):
																					if self.graph[u].count([w, v]       ) == 0:
																												self.graph[u].append([w, v]       )
														else:
																					__snake_case	:    Tuple											=     [[w, v]]
														if not self.graph.get(lowerCamelCase__       ):
																					__snake_case	:    Optional[int]											=     []

							def 					__snake_case      (							self :						Dict       )			->					str:
														return list(self.graph       )

							def 					__snake_case      (							self :						Dict					,			lowerCamelCase :						Dict					,			lowerCamelCase :						List[str]       )			->					str:






														if self.graph.get(lowerCamelCase__       ):
																					for _ in self.graph[u]:
																												if _[1] == v:
																																			self.graph[u].remove(lowerCamelCase__       )

							def 					__snake_case      (							self :						int					,			lowerCamelCase :						List[str]=-2					,			lowerCamelCase :						str=-1       )			->					int:






														if s == d:
																					return []
														__snake_case	:    Dict											=     []
														__snake_case	:    Union[str, Any]											=     []
														if s == -2:
																					__snake_case	:    Tuple											=     list(self.graph       )[0]
														stack.append(lowerCamelCase__       )
														visited.append(lowerCamelCase__       )
														__snake_case	:    Optional[int]											=     s

														while True:
																					# check if there is any non isolated nodes
																					if len(self.graph[s]       ) != 0:
																												__snake_case	:    int											=     s
																												for node in self.graph[s]:
																																			if visited.count(node[1]       ) < 1:
																																										if node[1] == d:
																																																	visited.append(lowerCamelCase__       )
																																																	return visited
																																										else:
																																																	stack.append(node[1]       )
																																																	visited.append(node[1]       )
																																																	__snake_case	:    List[str]											=     node[1]
																																																	break

																																																	 # check if all the children are visited
																					if s == ss:
																												stack.pop()
																												if len(lowerCamelCase__       ) != 0:
																																			__snake_case	:    str											=     stack[len(lowerCamelCase__       ) - 1]
																					else:
																												__snake_case	:    Optional[Any]											=     ss

																					# check if se have reached the starting point
																					if len(lowerCamelCase__       ) == 0:
																												return visited

							def 					__snake_case      (							self :						Tuple					,			lowerCamelCase :						Optional[Any]=-1       )			->					Union[str, Any]:






														if c == -1:
																					__snake_case	:    Any											=     floor(random() * 10000       ) + 10
														for i in range(lowerCamelCase__       ):
																					# every vertex has max 100 edges
																					for _ in range(floor(random() * 102       ) + 1       ):
																												__snake_case	:    Optional[int]											=     floor(random() * c       ) + 1
																												if n != i:
																																			self.add_pair(lowerCamelCase__					,			lowerCamelCase__					,			1       )

							def 					__snake_case      (							self :						int					,			lowerCamelCase :						Dict=-2       )			->					Any:
														__snake_case	:    Tuple											=     deque()
														__snake_case	:    List[Any]											=     []
														if s == -2:
																					__snake_case	:    List[str]											=     list(self.graph       )[0]
														d.append(lowerCamelCase__       )
														visited.append(lowerCamelCase__       )
														while d:
																					__snake_case	:    Dict											=     d.popleft()
																					if len(self.graph[s]       ) != 0:
																												for node in self.graph[s]:
																																			if visited.count(node[1]       ) < 1:
																																										d.append(node[1]       )
																																										visited.append(node[1]       )
														return visited

							def 					__snake_case      (							self :						List[str]					,			lowerCamelCase :						int       )			->					List[str]:
														__snake_case	:    Optional[Any]											=     0
														for x in self.graph:
																					for y in self.graph[x]:
																												if y[1] == u:
																																			count += 1
														return count

							def 					__snake_case      (							self :						Optional[int]					,			lowerCamelCase :						int       )			->					List[Any]:
														return len(self.graph[u]       )

							def 					__snake_case      (							self :						Optional[int]					,			lowerCamelCase :						Dict=-2       )			->					Optional[Any]:
														__snake_case	:    Any											=     []
														__snake_case	:    List[str]											=     []
														if s == -2:
																					__snake_case	:    Union[str, Any]											=     list(self.graph       )[0]
														stack.append(lowerCamelCase__       )
														visited.append(lowerCamelCase__       )
														__snake_case	:    str											=     s
														__snake_case	:    str											=     []

														while True:
																					# check if there is any non isolated nodes
																					if len(self.graph[s]       ) != 0:
																												__snake_case	:    Tuple											=     s
																												for node in self.graph[s]:
																																			if visited.count(node[1]       ) < 1:
																																										stack.append(node[1]       )
																																										visited.append(node[1]       )
																																										__snake_case	:    str											=     node[1]
																																										break

																																										  # check if all the children are visited
																					if s == ss:
																												sorted_nodes.append(stack.pop()       )
																												if len(lowerCamelCase__       ) != 0:
																																			__snake_case	:    Any											=     stack[len(lowerCamelCase__       ) - 1]
																					else:
																												__snake_case	:    Dict											=     ss

																					# check if se have reached the starting point
																					if len(lowerCamelCase__       ) == 0:
																												return sorted_nodes

							def 					__snake_case      (							self :						Dict       )			->					Optional[int]:
														__snake_case	:    Any											=     []
														__snake_case	:    Optional[Any]											=     []
														__snake_case	:    Any											=     list(self.graph       )[0]
														stack.append(lowerCamelCase__       )
														visited.append(lowerCamelCase__       )
														__snake_case	:    Optional[int]											=     -2
														__snake_case	:    Optional[int]											=     []
														__snake_case	:    List[Any]											=     s
														__snake_case	:    List[Any]											=     False
														__snake_case	:    List[str]											=     set()

														while True:
																					# check if there is any non isolated nodes
																					if len(self.graph[s]       ) != 0:
																												__snake_case	:    List[str]											=     s
																												for node in self.graph[s]:
																																			if (
																																			    visited.count(node[1]       ) > 0
																																			    and node[1] != parent
																																			    and indirect_parents.count(node[1]       ) > 0
																																			    and not on_the_way_back
																																			):
																																										__snake_case	:    Optional[int]											=     len(lowerCamelCase__       ) - 1
																																										while len_stack >= 0:
																																																	if stack[len_stack] == node[1]:
																																																								anticipating_nodes.add(node[1]       )
																																																								break
																																																	else:
																																																								anticipating_nodes.add(stack[len_stack]       )
																																																								len_stack -= 1
																																			if visited.count(node[1]       ) < 1:
																																										stack.append(node[1]       )
																																										visited.append(node[1]       )
																																										__snake_case	:    Union[str, Any]											=     node[1]
																																										break

																																										  # check if all the children are visited
																					if s == ss:
																												stack.pop()
																												__snake_case	:    Tuple											=     True
																												if len(lowerCamelCase__       ) != 0:
																																			__snake_case	:    str											=     stack[len(lowerCamelCase__       ) - 1]
																					else:
																												__snake_case	:    Optional[Any]											=     False
																												indirect_parents.append(lowerCamelCase__       )
																												__snake_case	:    int											=     s
																												__snake_case	:    Tuple											=     ss

																					# check if se have reached the starting point
																					if len(lowerCamelCase__       ) == 0:
																												return list(lowerCamelCase__       )

							def 					__snake_case      (							self :						Optional[Any]       )			->					Optional[Any]:
														__snake_case	:    int											=     []
														__snake_case	:    Optional[int]											=     []
														__snake_case	:    Tuple											=     list(self.graph       )[0]
														stack.append(lowerCamelCase__       )
														visited.append(lowerCamelCase__       )
														__snake_case	:    Tuple											=     -2
														__snake_case	:    str											=     []
														__snake_case	:    Any											=     s
														__snake_case	:    Union[str, Any]											=     False
														__snake_case	:    Union[str, Any]											=     set()

														while True:
																					# check if there is any non isolated nodes
																					if len(self.graph[s]       ) != 0:
																												__snake_case	:    List[Any]											=     s
																												for node in self.graph[s]:
																																			if (
																																			    visited.count(node[1]       ) > 0
																																			    and node[1] != parent
																																			    and indirect_parents.count(node[1]       ) > 0
																																			    and not on_the_way_back
																																			):
																																										__snake_case	:    Optional[Any]											=     len(lowerCamelCase__       ) - 1
																																										while len_stack_minus_one >= 0:
																																																	if stack[len_stack_minus_one] == node[1]:
																																																								anticipating_nodes.add(node[1]       )
																																																								break
																																																	else:
																																																								return True
																																			if visited.count(node[1]       ) < 1:
																																										stack.append(node[1]       )
																																										visited.append(node[1]       )
																																										__snake_case	:    Tuple											=     node[1]
																																										break

																																										  # check if all the children are visited
																					if s == ss:
																												stack.pop()
																												__snake_case	:    Any											=     True
																												if len(lowerCamelCase__       ) != 0:
																																			__snake_case	:    Dict											=     stack[len(lowerCamelCase__       ) - 1]
																					else:
																												__snake_case	:    Any											=     False
																												indirect_parents.append(lowerCamelCase__       )
																												__snake_case	:    List[str]											=     s
																												__snake_case	:    Union[str, Any]											=     ss

																					# check if se have reached the starting point
																					if len(lowerCamelCase__       ) == 0:
																												return False

							def 					__snake_case      (							self :						Tuple					,			lowerCamelCase :						str=-2					,			lowerCamelCase :						Union[str, Any]=-1       )			->					List[Any]:
														__snake_case	:    str											=     time()
														self.dfs(lowerCamelCase__					,			lowerCamelCase__       )
														__snake_case	:    List[Any]											=     time()
														return end - begin






							def 					__snake_case      (							self :						Any					,			lowerCamelCase :						Dict=-2       )			->					Tuple:
														__snake_case	:    Any											=     time()
														self.bfs(lowerCamelCase__       )
														__snake_case	:    str											=     time()
														return end - begin

class        a	:




							"""simple docstring"""


							def __init__(							self :						int       )			->					Union[str, Any]:
														__snake_case	:    int											=     {}

							def 					__snake_case      (							self :						List[Any]					,			lowerCamelCase :						List[str]					,			lowerCamelCase :						str					,			lowerCamelCase :						Optional[int]=1       )			->					Any:






														if self.graph.get(lowerCamelCase__       ):
																					# if there already is a edge
																					if self.graph[u].count([w, v]       ) == 0:
																												self.graph[u].append([w, v]       )
														else:
																					# if u does not exist
																					__snake_case	:    Optional[Any]											=     [[w, v]]
														# add the other way
														if self.graph.get(lowerCamelCase__       ):
																					# if there already is a edge
																					if self.graph[v].count([w, u]       ) == 0:
																												self.graph[v].append([w, u]       )
														else:
																					# if u does not exist
																					__snake_case	:    int											=     [[w, u]]

							def 					__snake_case      (							self :						Dict					,			lowerCamelCase :						List[str]					,			lowerCamelCase :						Optional[int]       )			->					List[Any]:






														if self.graph.get(lowerCamelCase__       ):
																					for _ in self.graph[u]:
																												if _[1] == v:
																																			self.graph[u].remove(lowerCamelCase__       )
																												# the other way round
														if self.graph.get(lowerCamelCase__       ):
																					for _ in self.graph[v]:
																												if _[1] == u:
																																			self.graph[v].remove(lowerCamelCase__       )

							def 					__snake_case      (							self :						List[Any]					,			lowerCamelCase :						int=-2					,			lowerCamelCase :						int=-1       )			->					Optional[int]:






														if s == d:
																					return []
														__snake_case	:    Any											=     []
														__snake_case	:    Optional[int]											=     []
														if s == -2:
																					__snake_case	:    List[str]											=     list(self.graph       )[0]
														stack.append(lowerCamelCase__       )
														visited.append(lowerCamelCase__       )
														__snake_case	:    List[str]											=     s

														while True:
																					# check if there is any non isolated nodes
																					if len(self.graph[s]       ) != 0:
																												__snake_case	:    List[Any]											=     s
																												for node in self.graph[s]:
																																			if visited.count(node[1]       ) < 1:
																																										if node[1] == d:
																																																	visited.append(lowerCamelCase__       )
																																																	return visited
																																										else:
																																																	stack.append(node[1]       )
																																																	visited.append(node[1]       )
																																																	__snake_case	:    int											=     node[1]
																																																	break

																																																	 # check if all the children are visited
																					if s == ss:
																												stack.pop()
																												if len(lowerCamelCase__       ) != 0:
																																			__snake_case	:    Union[str, Any]											=     stack[len(lowerCamelCase__       ) - 1]
																					else:
																												__snake_case	:    Dict											=     ss

																					# check if se have reached the starting point
																					if len(lowerCamelCase__       ) == 0:
																												return visited

							def 					__snake_case      (							self :						List[Any]					,			lowerCamelCase :						List[Any]=-1       )			->					int:






														if c == -1:
																					__snake_case	:    Union[str, Any]											=     floor(random() * 10000       ) + 10
														for i in range(lowerCamelCase__       ):
																					# every vertex has max 100 edges
																					for _ in range(floor(random() * 102       ) + 1       ):
																												__snake_case	:    Optional[Any]											=     floor(random() * c       ) + 1
																												if n != i:
																																			self.add_pair(lowerCamelCase__					,			lowerCamelCase__					,			1       )

							def 					__snake_case      (							self :						Union[str, Any]					,			lowerCamelCase :						str=-2       )			->					str:
														__snake_case	:    List[str]											=     deque()
														__snake_case	:    Optional[Any]											=     []
														if s == -2:
																					__snake_case	:    Dict											=     list(self.graph       )[0]
														d.append(lowerCamelCase__       )
														visited.append(lowerCamelCase__       )
														while d:
																					__snake_case	:    Optional[Any]											=     d.popleft()
																					if len(self.graph[s]       ) != 0:
																												for node in self.graph[s]:
																																			if visited.count(node[1]       ) < 1:
																																										d.append(node[1]       )
																																										visited.append(node[1]       )
														return visited

							def 					__snake_case      (							self :						Union[str, Any]					,			lowerCamelCase :						Optional[int]       )			->					Tuple:
														return len(self.graph[u]       )

							def 					__snake_case      (							self :						Dict       )			->					Union[str, Any]:
														__snake_case	:    Optional[Any]											=     []
														__snake_case	:    Any											=     []
														__snake_case	:    int											=     list(self.graph       )[0]
														stack.append(lowerCamelCase__       )
														visited.append(lowerCamelCase__       )
														__snake_case	:    Union[str, Any]											=     -2
														__snake_case	:    Any											=     []
														__snake_case	:    str											=     s
														__snake_case	:    str											=     False
														__snake_case	:    str											=     set()

														while True:
																					# check if there is any non isolated nodes
																					if len(self.graph[s]       ) != 0:
																												__snake_case	:    List[Any]											=     s
																												for node in self.graph[s]:
																																			if (
																																			    visited.count(node[1]       ) > 0
																																			    and node[1] != parent
																																			    and indirect_parents.count(node[1]       ) > 0
																																			    and not on_the_way_back
																																			):
																																										__snake_case	:    Any											=     len(lowerCamelCase__       ) - 1
																																										while len_stack >= 0:
																																																	if stack[len_stack] == node[1]:
																																																								anticipating_nodes.add(node[1]       )
																																																								break
																																																	else:
																																																								anticipating_nodes.add(stack[len_stack]       )
																																																								len_stack -= 1
																																			if visited.count(node[1]       ) < 1:
																																										stack.append(node[1]       )
																																										visited.append(node[1]       )
																																										__snake_case	:    Union[str, Any]											=     node[1]
																																										break

																																										  # check if all the children are visited
																					if s == ss:
																												stack.pop()
																												__snake_case	:    str											=     True
																												if len(lowerCamelCase__       ) != 0:
																																			__snake_case	:    Optional[int]											=     stack[len(lowerCamelCase__       ) - 1]
																					else:
																												__snake_case	:    Optional[int]											=     False
																												indirect_parents.append(lowerCamelCase__       )
																												__snake_case	:    Dict											=     s
																												__snake_case	:    Union[str, Any]											=     ss

																					# check if se have reached the starting point
																					if len(lowerCamelCase__       ) == 0:
																												return list(lowerCamelCase__       )

							def 					__snake_case      (							self :						Dict       )			->					List[Any]:
														__snake_case	:    Optional[Any]											=     []
														__snake_case	:    Dict											=     []
														__snake_case	:    Tuple											=     list(self.graph       )[0]
														stack.append(lowerCamelCase__       )
														visited.append(lowerCamelCase__       )
														__snake_case	:    Any											=     -2
														__snake_case	:    Any											=     []
														__snake_case	:    Tuple											=     s
														__snake_case	:    List[Any]											=     False
														__snake_case	:    Optional[int]											=     set()

														while True:
																					# check if there is any non isolated nodes
																					if len(self.graph[s]       ) != 0:
																												__snake_case	:    Union[str, Any]											=     s
																												for node in self.graph[s]:
																																			if (
																																			    visited.count(node[1]       ) > 0
																																			    and node[1] != parent
																																			    and indirect_parents.count(node[1]       ) > 0
																																			    and not on_the_way_back
																																			):
																																										__snake_case	:    List[Any]											=     len(lowerCamelCase__       ) - 1
																																										while len_stack_minus_one >= 0:
																																																	if stack[len_stack_minus_one] == node[1]:
																																																								anticipating_nodes.add(node[1]       )
																																																								break
																																																	else:
																																																								return True
																																			if visited.count(node[1]       ) < 1:
																																										stack.append(node[1]       )
																																										visited.append(node[1]       )
																																										__snake_case	:    List[str]											=     node[1]
																																										break

																																										  # check if all the children are visited
																					if s == ss:
																												stack.pop()
																												__snake_case	:    Any											=     True
																												if len(lowerCamelCase__       ) != 0:
																																			__snake_case	:    int											=     stack[len(lowerCamelCase__       ) - 1]
																					else:
																												__snake_case	:    str											=     False
																												indirect_parents.append(lowerCamelCase__       )
																												__snake_case	:    Optional[Any]											=     s
																												__snake_case	:    Dict											=     ss

																					# check if se have reached the starting point
																					if len(lowerCamelCase__       ) == 0:
																												return False

							def 					__snake_case      (							self :						Union[str, Any]       )			->					Tuple:
														return list(self.graph       )

							def 					__snake_case      (							self :						Optional[Any]					,			lowerCamelCase :						Tuple=-2					,			lowerCamelCase :						str=-1       )			->					List[str]:
														__snake_case	:    List[Any]											=     time()
														self.dfs(lowerCamelCase__					,			lowerCamelCase__       )
														__snake_case	:    Union[str, Any]											=     time()
														return end - begin






							def 					__snake_case      (							self :						Optional[int]					,			lowerCamelCase :						List[Any]=-2       )			->					Union[str, Any]:
														__snake_case	:    Any											=     time()
														self.bfs(lowerCamelCase__       )
														__snake_case	:    str											=     time()
														return end - begin





from __future__ import annotations

_snake_case  :	Union[str, Any]			      =       {
    "A": ["B", "C", "E"],
    "B": ["A", "D", "E"],
    "C": ["A", "F", "G"],
    "D": ["B"],
    "E": ["A", "B", "D"],
    "F": ["C"],
    "G": ["C"],
}

class        a	:




							"""simple docstring"""


							def __init__(							self :						Tuple					,			lowerCamelCase :						dict[str, list[str]]					,			lowerCamelCase :						str       )			->					None:
														__snake_case	:    Tuple											=     graph
														# mapping node to its parent in resulting breadth first tree
														__snake_case	:    dict[str, str | None]											=     {}
														__snake_case	:    Dict											=     source_vertex

							def 					__snake_case      (							self :						Optional[int]       )			->					None:
														__snake_case	:    Dict											=     {self.source_vertex}
														__snake_case	:    List[str]											=     None
														__snake_case	:    Optional[Any]											=     [self.source_vertex]  # first in first out queue

														while queue:
																					__snake_case	:    List[Any]											=     queue.pop(0       )
																					for adjacent_vertex in self.graph[vertex]:
																												if adjacent_vertex not in visited:
																																			visited.add(lowerCamelCase       )
																																			__snake_case	:    Any											=     vertex
																																			queue.append(lowerCamelCase       )






							def 					__snake_case      (							self :						Optional[Any]					,			lowerCamelCase :						str       )			->					str:
														if target_vertex == self.source_vertex:
																					return self.source_vertex

														__snake_case	:    Optional[Any]											=     self.parent.get(lowerCamelCase       )
														if target_vertex_parent is None:
																					__snake_case	:    Optional[Any]											=     (
																					    F'No path from vertex: {self.source_vertex} to vertex: {target_vertex}'
																					)
																					raise ValueError(lowerCamelCase       )

														return self.shortest_path(lowerCamelCase       ) + F'->{target_vertex}'


if __name__ == "__main__":
			_snake_case  :	Optional[Any]			      =       Graph(graph, "G")
			g.breath_first_search()
			print(g.shortest_path("D"))
			print(g.shortest_path("G"))
			print(g.shortest_path("Foo"))

