


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






class     UpperCamelCase:


					def __init__(						self	:		List[str]						)			->	List[str]:




											'''simple docstring'''

											__snake_case				=		{}


					def 							SCREAMING_SNAKE_CASE_  (						self	:		int     ,    SCREAMING_SNAKE_CASE	:		Optional[Any]     ,    SCREAMING_SNAKE_CASE	:		Optional[Any]     ,    SCREAMING_SNAKE_CASE	:		Union[str, Any]=1						)			->	str:




											'''simple docstring'''

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


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Union[str, Any]						)			->	str:




											'''simple docstring'''

											return list(self.graph						)


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Tuple     ,    SCREAMING_SNAKE_CASE	:		List[Any]     ,    SCREAMING_SNAKE_CASE	:		List[str]						)			->	Union[str, Any]:




											'''simple docstring'''

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


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Union[str, Any]     ,    SCREAMING_SNAKE_CASE	:		Optional[Any]=-2     ,    SCREAMING_SNAKE_CASE	:		Any=-1						)			->	Union[str, Any]:




											'''simple docstring'''

											if s == d:
																	return []
											__snake_case				=		[]
											__snake_case				=		[]
											if s == -2:
																	__snake_case				=		list(self.graph						)[0]
											stack.append(SCREAMING_SNAKE_CASE						)
											visited.append(SCREAMING_SNAKE_CASE						)
											__snake_case				=		s

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

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

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


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Any     ,    SCREAMING_SNAKE_CASE	:		Union[str, Any]=-1						)			->	List[str]:




											'''simple docstring'''

											if c == -1:
																	__snake_case				=		floor(random() * 1_0_0_0_0						) + 1_0
											for i in range(SCREAMING_SNAKE_CASE						):
																	# every vertex has max 100 edges
																	for _ in range(floor(random() * 1_0_2						) + 1						):
																							__snake_case				=		floor(random() * c						) + 1
																							if n != i:
																													self.add_pair(SCREAMING_SNAKE_CASE     ,    SCREAMING_SNAKE_CASE     ,    1						)


					def 							SCREAMING_SNAKE_CASE_  (						self	:		List[str]     ,    SCREAMING_SNAKE_CASE	:		Union[str, Any]=-2						)			->	Any:




											'''simple docstring'''

											__snake_case				=		deque()
											__snake_case				=		[]
											if s == -2:
																	__snake_case				=		list(self.graph						)[0]
											d.append(SCREAMING_SNAKE_CASE						)
											visited.append(SCREAMING_SNAKE_CASE						)
											while d:
																	__snake_case				=		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 							SCREAMING_SNAKE_CASE_  (						self	:		Tuple     ,    SCREAMING_SNAKE_CASE	:		Any						)			->	str:




											'''simple docstring'''

											__snake_case				=		0
											for x in self.graph:
																	for y in self.graph[x]:
																							if y[1] == u:
																													count += 1
											return count


					def 							SCREAMING_SNAKE_CASE_  (						self	:		List[str]     ,    SCREAMING_SNAKE_CASE	:		str						)			->	Union[str, Any]:




											'''simple docstring'''

											return len(self.graph[u]						)


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Optional[int]     ,    SCREAMING_SNAKE_CASE	:		Optional[int]=-2						)			->	Optional[int]:




											'''simple docstring'''

											__snake_case				=		[]
											__snake_case				=		[]
											if s == -2:
																	__snake_case				=		list(self.graph						)[0]
											stack.append(SCREAMING_SNAKE_CASE						)
											visited.append(SCREAMING_SNAKE_CASE						)
											__snake_case				=		s
											__snake_case				=		[]

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

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

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


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Any						)			->	List[str]:




											'''simple docstring'''

											__snake_case				=		[]
											__snake_case				=		[]
											__snake_case				=		list(self.graph						)[0]
											stack.append(SCREAMING_SNAKE_CASE						)
											visited.append(SCREAMING_SNAKE_CASE						)
											__snake_case				=		-2
											__snake_case				=		[]
											__snake_case				=		s
											__snake_case				=		False
											__snake_case				=		set()

											while True:
																	# check if there is any non isolated nodes
																	if len(self.graph[s]						) != 0:
																							__snake_case				=		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				=		len(SCREAMING_SNAKE_CASE						) - 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				=		node[1]
																																			break

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

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


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Tuple						)			->	int:




											'''simple docstring'''

											__snake_case				=		[]
											__snake_case				=		[]
											__snake_case				=		list(self.graph						)[0]
											stack.append(SCREAMING_SNAKE_CASE						)
											visited.append(SCREAMING_SNAKE_CASE						)
											__snake_case				=		-2
											__snake_case				=		[]
											__snake_case				=		s
											__snake_case				=		False
											__snake_case				=		set()

											while True:
																	# check if there is any non isolated nodes
																	if len(self.graph[s]						) != 0:
																							__snake_case				=		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				=		len(SCREAMING_SNAKE_CASE						) - 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				=		node[1]
																																			break

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

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


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Dict     ,    SCREAMING_SNAKE_CASE	:		Tuple=-2     ,    SCREAMING_SNAKE_CASE	:		int=-1						)			->	int:




											'''simple docstring'''

											__snake_case				=		time()
											self.dfs(SCREAMING_SNAKE_CASE     ,    SCREAMING_SNAKE_CASE						)
											__snake_case				=		time()
											return end - begin






					def 							SCREAMING_SNAKE_CASE_  (						self	:		int     ,    SCREAMING_SNAKE_CASE	:		int=-2						)			->	Dict:




											'''simple docstring'''

											__snake_case				=		time()
											self.bfs(SCREAMING_SNAKE_CASE						)
											__snake_case				=		time()
											return end - begin






class     UpperCamelCase:


					def __init__(						self	:		List[str]						)			->	str:




											'''simple docstring'''

											__snake_case				=		{}


					def 							SCREAMING_SNAKE_CASE_  (						self	:		List[Any]     ,    SCREAMING_SNAKE_CASE	:		str     ,    SCREAMING_SNAKE_CASE	:		List[str]     ,    SCREAMING_SNAKE_CASE	:		Union[str, Any]=1						)			->	List[str]:




											'''simple docstring'''

											if self.graph.get(SCREAMING_SNAKE_CASE						):
																	# 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				=		[[w, v]]
											# add the other way
											if self.graph.get(SCREAMING_SNAKE_CASE						):
																	# 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				=		[[w, u]]


					def 							SCREAMING_SNAKE_CASE_  (						self	:		str     ,    SCREAMING_SNAKE_CASE	:		Optional[int]     ,    SCREAMING_SNAKE_CASE	:		int						)			->	List[str]:




											'''simple docstring'''

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


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Any     ,    SCREAMING_SNAKE_CASE	:		List[str]=-2     ,    SCREAMING_SNAKE_CASE	:		Optional[int]=-1						)			->	List[str]:




											'''simple docstring'''

											if s == d:
																	return []
											__snake_case				=		[]
											__snake_case				=		[]
											if s == -2:
																	__snake_case				=		list(self.graph						)[0]
											stack.append(SCREAMING_SNAKE_CASE						)
											visited.append(SCREAMING_SNAKE_CASE						)
											__snake_case				=		s

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

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

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


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Optional[Any]     ,    SCREAMING_SNAKE_CASE	:		List[str]=-1						)			->	List[str]:




											'''simple docstring'''

											if c == -1:
																	__snake_case				=		floor(random() * 1_0_0_0_0						) + 1_0
											for i in range(SCREAMING_SNAKE_CASE						):
																	# every vertex has max 100 edges
																	for _ in range(floor(random() * 1_0_2						) + 1						):
																							__snake_case				=		floor(random() * c						) + 1
																							if n != i:
																													self.add_pair(SCREAMING_SNAKE_CASE     ,    SCREAMING_SNAKE_CASE     ,    1						)


					def 							SCREAMING_SNAKE_CASE_  (						self	:		List[str]     ,    SCREAMING_SNAKE_CASE	:		Dict=-2						)			->	Dict:




											'''simple docstring'''

											__snake_case				=		deque()
											__snake_case				=		[]
											if s == -2:
																	__snake_case				=		list(self.graph						)[0]
											d.append(SCREAMING_SNAKE_CASE						)
											visited.append(SCREAMING_SNAKE_CASE						)
											while d:
																	__snake_case				=		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 							SCREAMING_SNAKE_CASE_  (						self	:		Tuple     ,    SCREAMING_SNAKE_CASE	:		Union[str, Any]						)			->	Optional[int]:




											'''simple docstring'''

											return len(self.graph[u]						)


					def 							SCREAMING_SNAKE_CASE_  (						self	:		int						)			->	List[Any]:




											'''simple docstring'''

											__snake_case				=		[]
											__snake_case				=		[]
											__snake_case				=		list(self.graph						)[0]
											stack.append(SCREAMING_SNAKE_CASE						)
											visited.append(SCREAMING_SNAKE_CASE						)
											__snake_case				=		-2
											__snake_case				=		[]
											__snake_case				=		s
											__snake_case				=		False
											__snake_case				=		set()

											while True:
																	# check if there is any non isolated nodes
																	if len(self.graph[s]						) != 0:
																							__snake_case				=		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				=		len(SCREAMING_SNAKE_CASE						) - 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				=		node[1]
																																			break

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

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


					def 							SCREAMING_SNAKE_CASE_  (						self	:		List[Any]						)			->	Optional[Any]:




											'''simple docstring'''

											__snake_case				=		[]
											__snake_case				=		[]
											__snake_case				=		list(self.graph						)[0]
											stack.append(SCREAMING_SNAKE_CASE						)
											visited.append(SCREAMING_SNAKE_CASE						)
											__snake_case				=		-2
											__snake_case				=		[]
											__snake_case				=		s
											__snake_case				=		False
											__snake_case				=		set()

											while True:
																	# check if there is any non isolated nodes
																	if len(self.graph[s]						) != 0:
																							__snake_case				=		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				=		len(SCREAMING_SNAKE_CASE						) - 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				=		node[1]
																																			break

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

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


					def 							SCREAMING_SNAKE_CASE_  (						self	:		List[str]						)			->	str:




											'''simple docstring'''

											return list(self.graph						)


					def 							SCREAMING_SNAKE_CASE_  (						self	:		int     ,    SCREAMING_SNAKE_CASE	:		str=-2     ,    SCREAMING_SNAKE_CASE	:		Union[str, Any]=-1						)			->	Dict:




											'''simple docstring'''

											__snake_case				=		time()
											self.dfs(SCREAMING_SNAKE_CASE     ,    SCREAMING_SNAKE_CASE						)
											__snake_case				=		time()
											return end - begin






					def 							SCREAMING_SNAKE_CASE_  (						self	:		Union[str, Any]     ,    SCREAMING_SNAKE_CASE	:		Tuple=-2						)			->	Optional[Any]:




											'''simple docstring'''

											__snake_case				=		time()
											self.bfs(SCREAMING_SNAKE_CASE						)
											__snake_case				=		time()
											return end - begin









def 	_lowerCAmelCase       (    _lowerCAmelCase = "The quick brown fox jumps over the lazy dog"      ,	)						->	bool:


						'''simple docstring'''






						__snake_case				=		set()

						# Replace all the whitespace in our sentence
						__snake_case				=		input_str.replace(" "      ,	"" )
						for alpha in input_str:
												if "a" <= alpha.lower() <= "z":
																		frequency.add(alpha.lower() )
						return len(_lowerCAmelCase ) == 26





def 	_lowerCAmelCase       (    _lowerCAmelCase = "The quick brown fox jumps over the lazy dog"      ,	)						->	bool:


						'''simple docstring'''






						__snake_case				=		[False] * 26
						for char in input_str:
												if char.islower():
																		__snake_case				=		True
												elif char.isupper():
																		__snake_case				=		True
						return all(_lowerCAmelCase )





def 	_lowerCAmelCase       (    _lowerCAmelCase = "The quick brown fox jumps over the lazy dog"      ,	)						->	bool:


						'''simple docstring'''






						return len({char for char in input_str.lower() if char.isalpha()} ) == 26





def 	_lowerCAmelCase       (    )						->	None:


						'''simple docstring'''






						from timeit import timeit

						__snake_case				=		"from __main__ import is_pangram, is_pangram_faster, is_pangram_fastest"
						print(timeit("is_pangram()"      ,	setup=_lowerCAmelCase ) )
						print(timeit("is_pangram_faster()"      ,	setup=_lowerCAmelCase ) )
						print(timeit("is_pangram_fastest()"      ,	setup=_lowerCAmelCase ) )
						# 5.348480500048026, 2.6477354579837993, 1.8470395830227062
						# 5.036091582966037, 2.644472333951853,  1.8869528750656173


if __name__ == "__main__":
	import doctest

	doctest.testmod()
	benchmark()





