



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


class 				_a						:





							'''simple docstring'''

							def __init__(							self				):







											"""simple docstring"""



											a__	:							Optional[int]      						= {}



							def 		_A	(							self ,					__UpperCAmelCase ,					__UpperCAmelCase ,					__UpperCAmelCase=1				):







											"""simple docstring"""



											if self.graph.get(__UpperCAmelCase				):
															if self.graph[u].count([w, v]				) == 0:
																			self.graph[u].append([w, v]				)
											else:
															a__	:							Optional[Any]      						= [[w, v]]
											if not self.graph.get(__UpperCAmelCase				):
															a__	:							List[Any]      						= []



							def 		_A	(							self				):







											"""simple docstring"""



											return list(self.graph				)



							def 		_A	(							self ,					__UpperCAmelCase ,					__UpperCAmelCase				):







											"""simple docstring"""



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



							def 		_A	(							self ,					__UpperCAmelCase=-2 ,					__UpperCAmelCase=-1				):







											"""simple docstring"""



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

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

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

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



							def 		_A	(							self ,					__UpperCAmelCase=-1				):







											"""simple docstring"""



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



							def 		_A	(							self ,					__UpperCAmelCase=-2				):







											"""simple docstring"""



											a__	:							Any      						= deque()
											a__	:							List[Any]      						= []
											if s == -2:
															a__	:							Union[str, Any]      						= list(self.graph				)[0]
											d.append(__UpperCAmelCase				)
											visited.append(__UpperCAmelCase				)
											while d:
															a__	:							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 		_A	(							self ,					__UpperCAmelCase				):







											"""simple docstring"""



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



							def 		_A	(							self ,					__UpperCAmelCase				):







											"""simple docstring"""



											return len(self.graph[u]				)



							def 		_A	(							self ,					__UpperCAmelCase=-2				):







											"""simple docstring"""



											a__	:							int      						= []
											a__	:							Optional[int]      						= []
											if s == -2:
															a__	:							Any      						= list(self.graph				)[0]
											stack.append(__UpperCAmelCase				)
											visited.append(__UpperCAmelCase				)
											a__	:							Tuple      						= s
											a__	:							List[Any]      						= []

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

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

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



							def 		_A	(							self				):







											"""simple docstring"""



											a__	:							Tuple      						= []
											a__	:							Tuple      						= []
											a__	:							Tuple      						= list(self.graph				)[0]
											stack.append(__UpperCAmelCase				)
											visited.append(__UpperCAmelCase				)
											a__	:							Tuple      						= -2
											a__	:							List[str]      						= []
											a__	:							Optional[int]      						= s
											a__	:							Optional[int]      						= False
											a__	:							List[str]      						= set()

											while True:
															# check if there is any non isolated nodes
															if len(self.graph[s]				) != 0:
																			a__	:							Optional[int]      						= 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__	:							Union[str, Any]      						= 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__	:							List[str]      						= node[1]
																											break

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

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



							def 		_A	(							self				):







											"""simple docstring"""



											a__	:							List[str]      						= []
											a__	:							Tuple      						= []
											a__	:							int      						= list(self.graph				)[0]
											stack.append(__UpperCAmelCase				)
											visited.append(__UpperCAmelCase				)
											a__	:							Dict      						= -2
											a__	:							Tuple      						= []
											a__	:							Optional[int]      						= s
											a__	:							List[Any]      						= False
											a__	:							Union[str, Any]      						= set()

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

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

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



							def 		_A	(							self ,					__UpperCAmelCase=-2 ,					__UpperCAmelCase=-1				):







											"""simple docstring"""



											a__	:							Optional[Any]      						= time()
											self.dfs(__UpperCAmelCase ,					__UpperCAmelCase				)
											a__	:							Union[str, Any]      						= time()
											return end - begin




							def 		_A	(							self ,					__UpperCAmelCase=-2				):







											"""simple docstring"""



											a__	:							Optional[Any]      						= time()
											self.bfs(__UpperCAmelCase				)
											a__	:							Dict      						= time()
											return end - begin





class 				_a						:





							'''simple docstring'''

							def __init__(							self				):







											"""simple docstring"""



											a__	:							List[Any]      						= {}



							def 		_A	(							self ,					__UpperCAmelCase ,					__UpperCAmelCase ,					__UpperCAmelCase=1				):







											"""simple docstring"""



											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__	:							Optional[Any]      						= [[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__	:							Optional[Any]      						= [[w, u]]



							def 		_A	(							self ,					__UpperCAmelCase ,					__UpperCAmelCase				):







											"""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 		_A	(							self ,					__UpperCAmelCase=-2 ,					__UpperCAmelCase=-1				):







											"""simple docstring"""



											if s == d:
															return []
											a__	:							Optional[Any]      						= []
											a__	:							int      						= []
											if s == -2:
															a__	:							Tuple      						= list(self.graph				)[0]
											stack.append(__UpperCAmelCase				)
											visited.append(__UpperCAmelCase				)
											a__	:							Optional[int]      						= s

											while True:
															# check if there is any non isolated nodes
															if len(self.graph[s]				) != 0:
																			a__	:							Union[str, Any]      						= 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__	:							int      						= node[1]
																															break

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

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



							def 		_A	(							self ,					__UpperCAmelCase=-1				):







											"""simple docstring"""



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



							def 		_A	(							self ,					__UpperCAmelCase=-2				):







											"""simple docstring"""



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







											"""simple docstring"""



											return len(self.graph[u]				)



							def 		_A	(							self				):







											"""simple docstring"""



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

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

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

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



							def 		_A	(							self				):







											"""simple docstring"""



											a__	:							Optional[int]      						= []
											a__	:							Any      						= []
											a__	:							str      						= list(self.graph				)[0]
											stack.append(__UpperCAmelCase				)
											visited.append(__UpperCAmelCase				)
											a__	:							List[str]      						= -2
											a__	:							Optional[int]      						= []
											a__	:							List[str]      						= s
											a__	:							Tuple      						= False
											a__	:							Any      						= set()

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

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

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



							def 		_A	(							self				):







											"""simple docstring"""



											return list(self.graph				)



							def 		_A	(							self ,					__UpperCAmelCase=-2 ,					__UpperCAmelCase=-1				):







											"""simple docstring"""



											a__	:							Optional[Any]      						= time()
											self.dfs(__UpperCAmelCase ,					__UpperCAmelCase				)
											a__	:							Optional[int]      						= time()
											return end - begin




							def 		_A	(							self ,					__UpperCAmelCase=-2				):







											"""simple docstring"""



											a__	:							int      						= time()
											self.bfs(__UpperCAmelCase				)
											a__	:							Optional[int]      						= time()
											return end - begin







from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_sentencepiece_available


lowerCamelCase		       =      {}


try:
						if not is_sentencepiece_available():
												raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
						pass
else:
						lowerCamelCase		       =      ["""MLukeTokenizer"""]

if TYPE_CHECKING:
						try:
												if not is_sentencepiece_available():
																		raise OptionalDependencyNotAvailable()
						except OptionalDependencyNotAvailable:
												pass
						else:
												from .tokenization_mluke import MLukeTokenizer


else:
						import sys

						lowerCamelCase		       =      _LazyModule(__name__, globals()["""__file__"""], _import_structure, module_spec=__spec__)


