

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






class       __magic_name__       :





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




						'''simple docstring'''
						__a     ={}





			def 						__magic_name__       (						self   ,    __snake_case   ,    __snake_case   ,    __snake_case=1   )  ->					Dict:




						'''simple docstring'''
						if self.graph.get(__UpperCamelCase   ):
									if self.graph[u].count([w, v]   ) == 0:
												self.graph[u].append([w, v]   )
						else:
									__a     =[[w, v]]
						if not self.graph.get(__UpperCamelCase   ):
									__a     =[]





			def 						__magic_name__       (						self   )  ->					Any:




						'''simple docstring'''
						return list(self.graph   )





			def 						__magic_name__       (						self   ,    __snake_case   ,    __snake_case   )  ->					Dict:




						'''simple docstring'''
						if self.graph.get(__UpperCamelCase   ):
									for _ in self.graph[u]:
												if _[1] == v:
															self.graph[u].remove(__UpperCamelCase   )





			def 						__magic_name__       (						self   ,    __snake_case=-2   ,    __snake_case=-1   )  ->					int:




						'''simple docstring'''
						if s == d:
									return []
						__a     =[]
						__a     =[]
						if s == -2:
									__a     =list(self.graph   )[0]
						stack.append(__UpperCamelCase   )
						visited.append(__UpperCamelCase   )
						__a     =s

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

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

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





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




						'''simple docstring'''
						if c == -1:
									__a     =floor(random() * 1_0000   ) + 10
						for i in range(__UpperCamelCase   ):
									# every vertex has max 100 edges
									for _ in range(floor(random() * 102   ) + 1   ):
												__a     =floor(random() * c   ) + 1
												if n != i:
															self.add_pair(__UpperCamelCase   ,    __UpperCamelCase   ,    1   )





			def 						__magic_name__       (						self   ,    __snake_case=-2   )  ->					Any:




						'''simple docstring'''
						__a     =deque()
						__a     =[]
						if s == -2:
									__a     =list(self.graph   )[0]
						d.append(__UpperCamelCase   )
						visited.append(__UpperCamelCase   )
						while d:
									__a     =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 						__magic_name__       (						self   ,    __snake_case   )  ->					str:




						'''simple docstring'''
						__a     =0
						for x in self.graph:
									for y in self.graph[x]:
												if y[1] == u:
															count += 1
						return count





			def 						__magic_name__       (						self   ,    __snake_case   )  ->					Optional[Any]:




						'''simple docstring'''
						return len(self.graph[u]   )





			def 						__magic_name__       (						self   ,    __snake_case=-2   )  ->					List[str]:




						'''simple docstring'''
						__a     =[]
						__a     =[]
						if s == -2:
									__a     =list(self.graph   )[0]
						stack.append(__UpperCamelCase   )
						visited.append(__UpperCamelCase   )
						__a     =s
						__a     =[]

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

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

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





			def 						__magic_name__       (						self   )  ->					int:




						'''simple docstring'''
						__a     =[]
						__a     =[]
						__a     =list(self.graph   )[0]
						stack.append(__UpperCamelCase   )
						visited.append(__UpperCamelCase   )
						__a     =-2
						__a     =[]
						__a     =s
						__a     =False
						__a     =set()

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

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

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





			def 						__magic_name__       (						self   )  ->					Optional[int]:




						'''simple docstring'''
						__a     =[]
						__a     =[]
						__a     =list(self.graph   )[0]
						stack.append(__UpperCamelCase   )
						visited.append(__UpperCamelCase   )
						__a     =-2
						__a     =[]
						__a     =s
						__a     =False
						__a     =set()

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

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

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





			def 						__magic_name__       (						self   ,    __snake_case=-2   ,    __snake_case=-1   )  ->					Dict:




						'''simple docstring'''
						__a     =time()
						self.dfs(__UpperCamelCase   ,    __UpperCamelCase   )
						__a     =time()
						return end - begin





			def 						__magic_name__       (						self   ,    __snake_case=-2   )  ->					Optional[int]:




						'''simple docstring'''
						__a     =time()
						self.bfs(__UpperCamelCase   )
						__a     =time()
						return end - begin






class       __magic_name__       :





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




						'''simple docstring'''
						__a     ={}





			def 						__magic_name__       (						self   ,    __snake_case   ,    __snake_case   ,    __snake_case=1   )  ->					Any:




						'''simple docstring'''
						# check if the u exists
						if self.graph.get(__UpperCamelCase   ):
									# 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
									__a     =[[w, v]]
						# add the other way
						if self.graph.get(__UpperCamelCase   ):
									# 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
									__a     =[[w, u]]





			def 						__magic_name__       (						self   ,    __snake_case   ,    __snake_case   )  ->					Dict:




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





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




						'''simple docstring'''
						if s == d:
									return []
						__a     =[]
						__a     =[]
						if s == -2:
									__a     =list(self.graph   )[0]
						stack.append(__UpperCamelCase   )
						visited.append(__UpperCamelCase   )
						__a     =s

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

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

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





			def 						__magic_name__       (						self   ,    __snake_case=-1   )  ->					Optional[Any]:




						'''simple docstring'''
						if c == -1:
									__a     =floor(random() * 1_0000   ) + 10
						for i in range(__UpperCamelCase   ):
									# every vertex has max 100 edges
									for _ in range(floor(random() * 102   ) + 1   ):
												__a     =floor(random() * c   ) + 1
												if n != i:
															self.add_pair(__UpperCamelCase   ,    __UpperCamelCase   ,    1   )





			def 						__magic_name__       (						self   ,    __snake_case=-2   )  ->					int:




						'''simple docstring'''
						__a     =deque()
						__a     =[]
						if s == -2:
									__a     =list(self.graph   )[0]
						d.append(__UpperCamelCase   )
						visited.append(__UpperCamelCase   )
						while d:
									__a     =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 						__magic_name__       (						self   ,    __snake_case   )  ->					Optional[Any]:




						'''simple docstring'''
						return len(self.graph[u]   )





			def 						__magic_name__       (						self   )  ->					str:




						'''simple docstring'''
						__a     =[]
						__a     =[]
						__a     =list(self.graph   )[0]
						stack.append(__UpperCamelCase   )
						visited.append(__UpperCamelCase   )
						__a     =-2
						__a     =[]
						__a     =s
						__a     =False
						__a     =set()

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

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

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





			def 						__magic_name__       (						self   )  ->					Optional[int]:




						'''simple docstring'''
						__a     =[]
						__a     =[]
						__a     =list(self.graph   )[0]
						stack.append(__UpperCamelCase   )
						visited.append(__UpperCamelCase   )
						__a     =-2
						__a     =[]
						__a     =s
						__a     =False
						__a     =set()

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

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

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





			def 						__magic_name__       (						self   )  ->					int:




						'''simple docstring'''
						return list(self.graph   )





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




						'''simple docstring'''
						__a     =time()
						self.dfs(__UpperCamelCase   ,    __UpperCamelCase   )
						__a     =time()
						return end - begin





			def 						__magic_name__       (						self   ,    __snake_case=-2   )  ->					Optional[Any]:




						'''simple docstring'''
						__a     =time()
						self.bfs(__UpperCamelCase   )
						__a     =time()
						return end - begin











from ...configuration_utils import PretrainedConfig
from ...utils import logging


__snake_case     :List[str]			       =logging.get_logger(__name__)

__snake_case     :int			       ={'openai-gpt': 'https://huggingface.co/openai-gpt/resolve/main/config.json'}



class        lowerCAmelCase__					(  _lowerCamelCase       ):
				A_   :     Optional[Any]								=     'openai-gpt'
				A_   :     Any								=     {
				    'max_position_embeddings': 'n_positions',
				    'hidden_size': 'n_embd',
				    'num_attention_heads': 'n_head',
				    'num_hidden_layers': 'n_layer',
				}


				def __init__(							self      :  List[Any]						, __UpperCamelCase      :  List[str]=40_478						, __UpperCamelCase      :  List[Any]=512						, __UpperCamelCase      :  List[Any]=768						, __UpperCamelCase      :  Optional[int]=12						, __UpperCamelCase      :  Dict=12						, __UpperCamelCase      :  List[str]="gelu"						, __UpperCamelCase      :  str=0.1						, __UpperCamelCase      :  Optional[Any]=0.1						, __UpperCamelCase      :  Union[str, Any]=0.1						, __UpperCamelCase      :  List[str]=1e-5						, __UpperCamelCase      :  List[Any]=0.0_2						, __UpperCamelCase      :  str="cls_index"						, __UpperCamelCase      :  int=True						, __UpperCamelCase      :  int=None						, __UpperCamelCase      :  Optional[int]=True						, __UpperCamelCase      :  Tuple=0.1						, **__UpperCamelCase      :  List[Any]						, )		->     List[str]:
											A      						=    vocab_size
											A      						=    n_positions
											A      						=    n_embd
											A      						=    n_layer
											A      						=    n_head
											A      						=    afn
											A      						=    resid_pdrop
											A      						=    embd_pdrop
											A      						=    attn_pdrop
											A      						=    layer_norm_epsilon
											A      						=    initializer_range
											A      						=    summary_type
											A      						=    summary_use_proj
											A      						=    summary_activation
											A      						=    summary_first_dropout
											A      						=    summary_proj_to_labels
											super().__init__(**__UpperCamelCase       )