
"""simple docstring"""


import unittest

from transformers import LiltConfig, is_torch_available
from transformers.testing_utils import require_torch, slow, torch_device

from ...generation.test_utils import GenerationTesterMixin
from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
		import torch

		from transformers import (
		    LiltForQuestionAnswering,
		    LiltForSequenceClassification,
		    LiltForTokenClassification,
		    LiltModel,
		)
		from transformers.models.lilt.modeling_lilt import LILT_PRETRAINED_MODEL_ARCHIVE_LIST







class 				lowerCAmelCase_				:



						'''simple docstring'''


						def __init__( self     :      List[str]  ,A_     :      Tuple  ,A_     :      str=13  ,A_     :      List[Any]=7  ,A_     :      Dict=True  ,A_     :      Optional[int]=True  ,A_     :      Optional[int]=True  ,A_     :      Any=True  ,A_     :      Any=99  ,A_     :      Optional[int]=24  ,A_     :      Tuple=2  ,A_     :      int=6  ,A_     :      Dict=37  ,A_     :      List[str]="gelu"  ,A_     :      str=0.1  ,A_     :      List[Any]=0.1  ,A_     :      Any=512  ,A_     :      Union[str, Any]=16  ,A_     :      int=2  ,A_     :      Optional[Any]=0.02  ,A_     :      Any=3  ,A_     :      Tuple=None  ,A_     :      Optional[int]=1000  ,)     ->   Union[str, Any]:
							A						   =   parent
							A						   =   batch_size
							A						   =   seq_length
							A						   =   is_training
							A						   =   use_input_mask
							A						   =   use_token_type_ids
							A						   =   use_labels
							A						   =   vocab_size
							A						   =   hidden_size
							A						   =   num_hidden_layers
							A						   =   num_attention_heads
							A						   =   intermediate_size
							A						   =   hidden_act
							A						   =   hidden_dropout_prob
							A						   =   attention_probs_dropout_prob
							A						   =   max_position_embeddings
							A						   =   type_vocab_size
							A						   =   type_sequence_label_size
							A						   =   initializer_range
							A						   =   num_labels
							A						   =   scope
							A						   =   range_bbox


						def 						_SCREAMING_SNAKE_CASE      ( self     :      str      )     ->   List[Any]:
							A						   =   ids_tensor([self.batch_size, self.seq_length]  ,self.vocab_size      )

							A						   =   ids_tensor([self.batch_size, self.seq_length, 4]  ,self.range_bbox      )
							# Ensure that bbox is legal
							for i in range(bbox.shape[0]      ):
								for j in range(bbox.shape[1]      ):
									if bbox[i, j, 3] < bbox[i, j, 1]:
										A						   =   bbox[i, j, 3]
										A						   =   bbox[i, j, 1]
										A						   =   t
									if bbox[i, j, 2] < bbox[i, j, 0]:
										A						   =   bbox[i, j, 2]
										A						   =   bbox[i, j, 0]
										A						   =   t

							A						   =   None
							if self.use_input_mask:
								A						   =   ids_tensor([self.batch_size, self.seq_length]  ,vocab_size=2      )

							A						   =   None
							if self.use_token_type_ids:
								A						   =   ids_tensor([self.batch_size, self.seq_length]  ,self.type_vocab_size      )

							A						   =   None
							A						   =   None
							if self.use_labels:
								A						   =   ids_tensor([self.batch_size]  ,self.type_sequence_label_size      )
								A						   =   ids_tensor([self.batch_size, self.seq_length]  ,self.num_labels      )

							A						   =   self.get_config()

							return config, input_ids, bbox, token_type_ids, input_mask, sequence_labels, token_labels


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[Any]      )     ->   str:
							return LiltConfig(
							    vocab_size=self.vocab_size  ,hidden_size=self.hidden_size  ,num_hidden_layers=self.num_hidden_layers  ,num_attention_heads=self.num_attention_heads  ,intermediate_size=self.intermediate_size  ,hidden_act=self.hidden_act  ,hidden_dropout_prob=self.hidden_dropout_prob  ,attention_probs_dropout_prob=self.attention_probs_dropout_prob  ,max_position_embeddings=self.max_position_embeddings  ,type_vocab_size=self.type_vocab_size  ,initializer_range=self.initializer_range  ,)


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any  ,A_     :      int  ,A_     :      Optional[int]  ,A_     :      str  ,A_     :      Union[str, Any]  ,A_     :      str  ,A_     :      Dict  ,A_     :      Tuple  ,)     ->   List[str]:
							A						   =   LiltModel(config=A_      )
							model.to(A_      )
							model.eval()
							A						   =   model(A_  ,bbox=A_  ,attention_mask=A_  ,token_type_ids=A_      )
							A						   =   model(A_  ,bbox=A_  ,token_type_ids=A_      )
							A						   =   model(A_  ,bbox=A_      )

							self.parent.assertEqual(result.last_hidden_state.shape  ,(self.batch_size, self.seq_length, self.hidden_size)      )
							self.parent.assertEqual(result.pooler_output.shape  ,(self.batch_size, self.hidden_size)      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      str  ,A_     :      Dict  ,A_     :      Union[str, Any]  ,A_     :      Tuple  ,A_     :      Dict  ,A_     :      List[str]  ,A_     :      Dict  ,A_     :      int  ,)     ->   Optional[Any]:
							A						   =   self.num_labels
							A						   =   LiltForTokenClassification(config=A_      )
							model.to(A_      )
							model.eval()
							A						   =   model(
							    A_  ,bbox=A_  ,attention_mask=A_  ,token_type_ids=A_  ,labels=A_      )
							self.parent.assertEqual(result.logits.shape  ,(self.batch_size, self.seq_length, self.num_labels)      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      int  ,A_     :      List[str]  ,A_     :      Dict  ,A_     :      Optional[int]  ,A_     :      Optional[int]  ,A_     :      Any  ,A_     :      Dict  ,A_     :      Dict  ,)     ->   List[Any]:
							A						   =   LiltForQuestionAnswering(config=A_      )
							model.to(A_      )
							model.eval()
							A						   =   model(
							    A_  ,bbox=A_  ,attention_mask=A_  ,token_type_ids=A_  ,start_positions=A_  ,end_positions=A_  ,)
							self.parent.assertEqual(result.start_logits.shape  ,(self.batch_size, self.seq_length)      )
							self.parent.assertEqual(result.end_logits.shape  ,(self.batch_size, self.seq_length)      )




						def 						_SCREAMING_SNAKE_CASE      ( self     :      int      )     ->   List[Any]:
							A						   =   self.prepare_config_and_inputs()
							(
							    (
							    A
							)   ,      (
							    A
							)   ,      (
							    A
							)   ,      (
							    A
							)   ,      (
							    A
							)   ,      (
							    A
							)   ,      (
							    A
							)   ,      
							)						   =   config_and_inputs
							A						   =   {
							    'input_ids': input_ids,
							    'bbox': bbox,
							    'token_type_ids': token_type_ids,
							    'attention_mask': input_mask,
							}
							return config, inputs_dict







@require_torch
class 				lowerCAmelCase_				(      _lowercase		,					_lowercase		,					_lowercase		,					unittest.TestCase    ):



						'''simple docstring'''


						_lowerCamelCase:    Union[str, Any]      =    (
						    (
						        LiltModel,
						        LiltForSequenceClassification,
						        LiltForTokenClassification,
						        LiltForQuestionAnswering,
						    )
						    if is_torch_available()
						    else ()
						)
						_lowerCamelCase:    str      =    (
						    {
						        '''feature-extraction''': LiltModel,
						        '''question-answering''': LiltForQuestionAnswering,
						        '''text-classification''': LiltForSequenceClassification,
						        '''token-classification''': LiltForTokenClassification,
						        '''zero-shot''': LiltForSequenceClassification,
						    }
						    if is_torch_available()
						    else {}
						)
						_lowerCamelCase:    Optional[Any]      =    False
						_lowerCamelCase:    List[str]      =    False


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any  ,A_     :      List[Any]  ,A_     :      Optional[Any]  ,A_     :      Any  ,A_     :      Dict  ,A_     :      Union[str, Any]      )     ->   int:
							return True


						def 						_SCREAMING_SNAKE_CASE      ( self     :      int      )     ->   Optional[int]:
							A						   =   LiltModelTester(self      )
							A						   =   ConfigTester(self  ,config_class=A_  ,hidden_size=37      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any      )     ->   Optional[int]:
							self.config_tester.run_common_tests()


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any      )     ->   Any:
							A						   =   self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_model(*A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[str]      )     ->   Tuple:
							A						   =   self.model_tester.prepare_config_and_inputs()
							for type in ["absolute", "relative_key", "relative_key_query"]:
								A						   =   type
								self.model_tester.create_and_check_model(*A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]      )     ->   List[Any]:
							A						   =   self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_for_token_classification(*A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[str]      )     ->   Any:
							A						   =   self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_for_question_answering(*A_      )




						@slow
						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[Any]      )     ->   List[Any]:
							for model_name in LILT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
								A						   =   LiltModel.from_pretrained(A_      )
								self.assertIsNotNone(A_      )







@require_torch
@slow
class 				lowerCAmelCase_				(      unittest.TestCase    ):



						'''simple docstring'''


						def 						_SCREAMING_SNAKE_CASE      ( self     :      int      )     ->   int:
							A						   =   LiltModel.from_pretrained('SCUT-DLVCLab/lilt-roberta-en-base'      ).to(A_      )

							A						   =   torch.tensor([[1, 2]]  ,device=A_      )
							A						   =   torch.tensor([[[1, 2, 3, 4], [5, 6, 7, 8]]]  ,device=A_      )

							# forward pass
							with torch.no_grad():
								A						   =   model(input_ids=A_  ,bbox=A_      )

							A						   =   torch.Size([1, 2, 768]      )
							A						   =   torch.tensor(
							    [[-0.06_53, 0.09_50, -0.00_61], [-0.05_45, 0.09_26, -0.03_24]]  ,device=A_  ,)

							self.assertTrue(outputs.last_hidden_state.shape  ,A_      )
							self.assertTrue(torch.allclose(outputs.last_hidden_state[0, :, :3]  ,A_  ,atol=1e-3      )      )

"""simple docstring"""


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







class 				lowerCAmelCase_				:



						'''simple docstring'''


						def __init__( self     :      Dict      )     ->   int:
							A						   =   {}


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any  ,A_     :      Union[str, Any]  ,A_     :      Any  ,A_     :      Optional[Any]=1      )     ->   int:
							if self.graph.get(A_      ):
								if self.graph[u].count([w, v]      ) == 0:
									self.graph[u].append([w, v]      )
							else:
								A						   =   [[w, v]]
							if not self.graph.get(A_      ):
								A						   =   []


						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[str]      )     ->   Optional[int]:
							return list(self.graph      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      Union[str, Any]  ,A_     :      Dict      )     ->   Optional[Any]:
							if self.graph.get(A_      ):
								for _ in self.graph[u]:
									if _[1] == v:
										self.graph[u].remove(A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any  ,A_     :      int=-2  ,A_     :      Dict=-1      )     ->   str:
							if s == d:
								return []
							A						   =   []
							A						   =   []
							if s == -2:
								A						   =   list(self.graph      )[0]
							stack.append(A_      )
							visited.append(A_      )
							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(A_      )
												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(A_      ) != 0:
										A						   =   stack[len(A_      ) - 1]
								else:
									A						   =   ss

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


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


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[Any]  ,A_     :      Union[str, Any]=-2      )     ->   Optional[Any]:
							A						   =   deque()
							A						   =   []
							if s == -2:
								A						   =   list(self.graph      )[0]
							d.append(A_      )
							visited.append(A_      )
							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 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      Tuple      )     ->   Any:
							A						   =   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     :      Dict  ,A_     :      Union[str, Any]      )     ->   str:
							return len(self.graph[u]      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[int]  ,A_     :      Union[str, Any]=-2      )     ->   Any:
							A						   =   []
							A						   =   []
							if s == -2:
								A						   =   list(self.graph      )[0]
							stack.append(A_      )
							visited.append(A_      )
							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(A_      ) != 0:
										A						   =   stack[len(A_      ) - 1]
								else:
									A						   =   ss

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


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[Any]      )     ->   Tuple:
							A						   =   []
							A						   =   []
							A						   =   list(self.graph      )[0]
							stack.append(A_      )
							visited.append(A_      )
							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(A_      ) - 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(A_      ) != 0:
										A						   =   stack[len(A_      ) - 1]
								else:
									A						   =   False
									indirect_parents.append(A_      )
									A						   =   s
									A						   =   ss

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


						def 						_SCREAMING_SNAKE_CASE      ( self     :      int      )     ->   Optional[int]:
							A						   =   []
							A						   =   []
							A						   =   list(self.graph      )[0]
							stack.append(A_      )
							visited.append(A_      )
							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(A_      ) - 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(A_      ) != 0:
										A						   =   stack[len(A_      ) - 1]
								else:
									A						   =   False
									indirect_parents.append(A_      )
									A						   =   s
									A						   =   ss

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


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Dict  ,A_     :      Tuple=-2  ,A_     :      List[str]=-1      )     ->   str:
							A						   =   time()
							self.dfs(A_  ,A_      )
							A						   =   time()
							return end - begin




						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[str]  ,A_     :      Union[str, Any]=-2      )     ->   Dict:
							A						   =   time()
							self.bfs(A_      )
							A						   =   time()
							return end - begin







class 				lowerCAmelCase_				:



						'''simple docstring'''


						def __init__( self     :      List[Any]      )     ->   Tuple:
							A						   =   {}


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any  ,A_     :      Optional[Any]  ,A_     :      str  ,A_     :      List[str]=1      )     ->   Dict:
							# check if the u exists
							if self.graph.get(A_      ):
								# 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(A_      ):
								# 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 						_SCREAMING_SNAKE_CASE      ( self     :      List[Any]  ,A_     :      List[Any]  ,A_     :      List[str]      )     ->   List[Any]:
							if self.graph.get(A_      ):
								for _ in self.graph[u]:
									if _[1] == v:
										self.graph[u].remove(A_      )
        # the other way round
							if self.graph.get(A_      ):
								for _ in self.graph[v]:
									if _[1] == u:
										self.graph[v].remove(A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[Any]  ,A_     :      List[str]=-2  ,A_     :      List[Any]=-1      )     ->   int:
							if s == d:
								return []
							A						   =   []
							A						   =   []
							if s == -2:
								A						   =   list(self.graph      )[0]
							stack.append(A_      )
							visited.append(A_      )
							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(A_      )
												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(A_      ) != 0:
										A						   =   stack[len(A_      ) - 1]
								else:
									A						   =   ss

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


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      Optional[int]=-1      )     ->   List[Any]:
							if c == -1:
								A						   =   floor(random() * 1_0000      ) + 10
							for i in range(A_      ):
								# every vertex has max 100 edges
								for _ in range(floor(random() * 102      ) + 1      ):
									A						   =   floor(random() * c      ) + 1
									if n != i:
										self.add_pair(A_  ,A_  ,1      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[Any]  ,A_     :      Dict=-2      )     ->   List[Any]:
							A						   =   deque()
							A						   =   []
							if s == -2:
								A						   =   list(self.graph      )[0]
							d.append(A_      )
							visited.append(A_      )
							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 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      Optional[Any]      )     ->   List[Any]:
							return len(self.graph[u]      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[str]      )     ->   List[Any]:
							A						   =   []
							A						   =   []
							A						   =   list(self.graph      )[0]
							stack.append(A_      )
							visited.append(A_      )
							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(A_      ) - 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(A_      ) != 0:
										A						   =   stack[len(A_      ) - 1]
								else:
									A						   =   False
									indirect_parents.append(A_      )
									A						   =   s
									A						   =   ss

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


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[int]      )     ->   Any:
							A						   =   []
							A						   =   []
							A						   =   list(self.graph      )[0]
							stack.append(A_      )
							visited.append(A_      )
							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(A_      ) - 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(A_      ) != 0:
										A						   =   stack[len(A_      ) - 1]
								else:
									A						   =   False
									indirect_parents.append(A_      )
									A						   =   s
									A						   =   ss

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


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Dict      )     ->   Any:
							return list(self.graph      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[int]  ,A_     :      Optional[Any]=-2  ,A_     :      List[str]=-1      )     ->   Any:
							A						   =   time()
							self.dfs(A_  ,A_      )
							A						   =   time()
							return end - begin




						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[Any]  ,A_     :      List[Any]=-2      )     ->   Union[str, Any]:
							A						   =   time()
							self.bfs(A_      )
							A						   =   time()
							return end - begin