





"""simple docstring"""






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




class 				__lowercase			:







		'''simple docstring'''




		def __init__(						self     ):
						__a :						Dict			       =  {}







		def  _lowerCamelCase		(						self	,			_UpperCAmelCase	,			_UpperCAmelCase	,			_UpperCAmelCase=1     ):




						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 :						Tuple			       =  []







		def  _lowerCamelCase		(						self     ):
						return list(self.graph     )







		def  _lowerCamelCase		(						self	,			_UpperCAmelCase	,			_UpperCAmelCase     ):




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







		def  _lowerCamelCase		(						self	,			_UpperCAmelCase=-2	,			_UpperCAmelCase=-1     ):




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

						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:
																						if node[1] == d:
																										visited.append(_UpperCAmelCase     )
																										return visited
																						else:
																										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()
														if len(_UpperCAmelCase     ) != 0:
																		__a :						int			       =  stack[len(_UpperCAmelCase     ) - 1]
										else:
														__a :						Union[str, Any]			       =  ss

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







		def  _lowerCamelCase		(						self	,			_UpperCAmelCase=-1     ):




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







		def  _lowerCamelCase		(						self	,			_UpperCAmelCase=-2     ):
						__a :						List[Any]			       =  deque()
						__a :						Optional[int]			       =  []
						if s == -2:
										__a :						Union[str, Any]			       =  list(self.graph     )[0]
						d.append(_UpperCAmelCase     )
						visited.append(_UpperCAmelCase     )
						while d:
										__a :						str			       =  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  _lowerCamelCase		(						self	,			_UpperCAmelCase     ):
						__a :						Dict			       =  0
						for x in self.graph:
										for y in self.graph[x]:
														if y[1] == u:
																		count += 1
						return count







		def  _lowerCamelCase		(						self	,			_UpperCAmelCase     ):
						return len(self.graph[u]     )







		def  _lowerCamelCase		(						self	,			_UpperCAmelCase=-2     ):
						__a :						Optional[int]			       =  []
						__a :						Any			       =  []
						if s == -2:
										__a :						Optional[int]			       =  list(self.graph     )[0]
						stack.append(_UpperCAmelCase     )
						visited.append(_UpperCAmelCase     )
						__a :						Any			       =  s
						__a :						List[str]			       =  []

						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:
																						stack.append(node[1]     )
																						visited.append(node[1]     )
																						__a :						Dict			       =  node[1]
																						break

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

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







		def  _lowerCamelCase		(						self     ):
						__a :						Any			       =  []
						__a :						Any			       =  []
						__a :						List[Any]			       =  list(self.graph     )[0]
						stack.append(_UpperCAmelCase     )
						visited.append(_UpperCAmelCase     )
						__a :						Union[str, Any]			       =  -2
						__a :						Optional[Any]			       =  []
						__a :						Dict			       =  s
						__a :						int			       =  False
						__a :						int			       =  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 :						int			       =  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 :						Any			       =  node[1]
																						break

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

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







		def  _lowerCamelCase		(						self     ):
						__a :						Optional[int]			       =  []
						__a :						Tuple			       =  []
						__a :						Optional[Any]			       =  list(self.graph     )[0]
						stack.append(_UpperCAmelCase     )
						visited.append(_UpperCAmelCase     )
						__a :						Optional[int]			       =  -2
						__a :						int			       =  []
						__a :						List[Any]			       =  s
						__a :						int			       =  False
						__a :						Optional[Any]			       =  set()

						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]     ) > 0
																		    and node[1] != parent
																		    and indirect_parents.count(node[1]     ) > 0
																		    and not on_the_way_back
																		):
																						__a :						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 :						Optional[Any]			       =  True
														if len(_UpperCAmelCase     ) != 0:
																		__a :						List[str]			       =  stack[len(_UpperCAmelCase     ) - 1]
										else:
														__a :						List[Any]			       =  False
														indirect_parents.append(_UpperCAmelCase     )
														__a :						Any			       =  s
														__a :						List[Any]			       =  ss

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







		def  _lowerCamelCase		(						self	,			_UpperCAmelCase=-2	,			_UpperCAmelCase=-1     ):
						__a :						Dict			       =  time()
						self.dfs(_UpperCAmelCase	,			_UpperCAmelCase     )
						__a :						Dict			       =  time()
						return end - begin







		def  _lowerCamelCase		(						self	,			_UpperCAmelCase=-2     ):
						__a :						List[str]			       =  time()
						self.bfs(_UpperCAmelCase     )
						__a :						Union[str, Any]			       =  time()
						return end - begin






class 				__lowercase			:







		'''simple docstring'''




		def __init__(						self     ):
						__a :						int			       =  {}







		def  _lowerCamelCase		(						self	,			_UpperCAmelCase	,			_UpperCAmelCase	,			_UpperCAmelCase=1     ):




						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 :						List[str]			       =  [[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[int]			       =  [[w, u]]







		def  _lowerCamelCase		(						self	,			_UpperCAmelCase	,			_UpperCAmelCase     ):




						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  _lowerCamelCase		(						self	,			_UpperCAmelCase=-2	,			_UpperCAmelCase=-1     ):




						if s == d:
										return []
						__a :						List[Any]			       =  []
						__a :						List[Any]			       =  []
						if s == -2:
										__a :						Union[str, Any]			       =  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 :						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 :						List[Any]			       =  node[1]
																										break

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

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







		def  _lowerCamelCase		(						self	,			_UpperCAmelCase=-1     ):




						if c == -1:
										__a :						Union[str, Any]			       =  floor(random() * 10000     ) + 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  _lowerCamelCase		(						self	,			_UpperCAmelCase=-2     ):
						__a :						Union[str, Any]			       =  deque()
						__a :						str			       =  []
						if s == -2:
										__a :						List[str]			       =  list(self.graph     )[0]
						d.append(_UpperCAmelCase     )
						visited.append(_UpperCAmelCase     )
						while d:
										__a :						str			       =  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  _lowerCamelCase		(						self	,			_UpperCAmelCase     ):
						return len(self.graph[u]     )







		def  _lowerCamelCase		(						self     ):
						__a :						List[str]			       =  []
						__a :						Optional[int]			       =  []
						__a :						Union[str, Any]			       =  list(self.graph     )[0]
						stack.append(_UpperCAmelCase     )
						visited.append(_UpperCAmelCase     )
						__a :						List[str]			       =  -2
						__a :						List[Any]			       =  []
						__a :						str			       =  s
						__a :						Optional[int]			       =  False
						__a :						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 :						List[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 :						Tuple			       =  node[1]
																						break

            # check if all the children are visited
										if s == ss:
														stack.pop()
														__a :						str			       =  True
														if len(_UpperCAmelCase     ) != 0:
																		__a :						Any			       =  stack[len(_UpperCAmelCase     ) - 1]
										else:
														__a :						List[Any]			       =  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 list(_UpperCAmelCase     )







		def  _lowerCamelCase		(						self     ):
						__a :						Any			       =  []
						__a :						Tuple			       =  []
						__a :						str			       =  list(self.graph     )[0]
						stack.append(_UpperCAmelCase     )
						visited.append(_UpperCAmelCase     )
						__a :						List[Any]			       =  -2
						__a :						Optional[Any]			       =  []
						__a :						Any			       =  s
						__a :						Dict			       =  False
						__a :						Optional[Any]			       =  set()

						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]     ) > 0
																		    and node[1] != parent
																		    and indirect_parents.count(node[1]     ) > 0
																		    and not on_the_way_back
																		):
																						__a :						List[str]			       =  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 :						Optional[Any]			       =  node[1]
																						break

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

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







		def  _lowerCamelCase		(						self     ):
						return list(self.graph     )







		def  _lowerCamelCase		(						self	,			_UpperCAmelCase=-2	,			_UpperCAmelCase=-1     ):
						__a :						Dict			       =  time()
						self.dfs(_UpperCAmelCase	,			_UpperCAmelCase     )
						__a :						Any			       =  time()
						return end - begin







		def  _lowerCamelCase		(						self	,			_UpperCAmelCase=-2     ):
						__a :						Union[str, Any]			       =  time()
						self.bfs(_UpperCAmelCase     )
						__a :						Optional[Any]			       =  time()
						return end - begin






"""simple docstring"""






from dataclasses import dataclass, field
from typing import ClassVar, Dict

from ..features import Features, Value
from .base import TaskTemplate




@dataclass(frozen=_UpperCamelCase							)
class 				__lowercase			(			_UpperCamelCase							):







					'''simple docstring'''




					__lowerCAmelCase  =  field(default='''language-modeling'''   ,      metadata={'''include_in_asdict_even_if_is_default''': True}							)

					__lowerCAmelCase  =  Features({'''text''': Value('''string'''							)}							)
					__lowerCAmelCase  =  Features({}							)
					__lowerCAmelCase  =  "text"







					@property
					def  _lowerCamelCase		(						self     ):
									return {self.text_column: "text"}