

"""simple docstring"""





import unittest

from transformers import SqueezeBertConfig, is_torch_available
from transformers.testing_utils import require_sentencepiece, require_tokenizers, require_torch, slow, torch_device

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
							import torch

							from transformers import (
							    SQUEEZEBERT_PRETRAINED_MODEL_ARCHIVE_LIST,
							    SqueezeBertForMaskedLM,
							    SqueezeBertForMultipleChoice,
							    SqueezeBertForQuestionAnswering,
							    SqueezeBertForSequenceClassification,
							    SqueezeBertForTokenClassification,
							    SqueezeBertModel,
							)







class 							SCREAMING_SNAKE_CASE   (						a_			):






					"""simple docstring"""



					def __init__(			self     :							List[str]  ,lowercase_     :							Any  ,lowercase_     :							Dict=1_3  ,lowercase_     :							str=7  ,lowercase_     :							List[Any]=True  ,lowercase_     :							List[Any]=True  ,lowercase_     :							List[str]=False  ,lowercase_     :							Any=True  ,lowercase_     :							Tuple=9_9  ,lowercase_     :							str=3_2  ,lowercase_     :							List[str]=5  ,lowercase_     :							str=4  ,lowercase_     :							Tuple=6_4  ,lowercase_     :							Optional[int]="gelu"  ,lowercase_     :							Dict=0.1  ,lowercase_     :							Optional[Any]=0.1  ,lowercase_     :							Any=5_1_2  ,lowercase_     :							int=1_6  ,lowercase_     :							str=2  ,lowercase_     :							Tuple=0.02  ,lowercase_     :							List[str]=3  ,lowercase_     :							Any=4  ,lowercase_     :							int=None  ,lowercase_     :							str=2  ,lowercase_     :							Optional[int]=2  ,lowercase_     :							int=2  ,lowercase_     :							List[str]=2  ,lowercase_     :							List[Any]=4  ,lowercase_     :							Union[str, Any]=1  ,):
						lowerCAmelCase__      :		List[Any]    							=      parent
						lowerCAmelCase__      :		int    							=      batch_size
						lowerCAmelCase__      :		Tuple    							=      seq_length
						lowerCAmelCase__      :		Tuple    							=      is_training
						lowerCAmelCase__      :		Any    							=      use_input_mask
						lowerCAmelCase__      :		Tuple    							=      use_token_type_ids
						lowerCAmelCase__      :		Optional[int]    							=      use_labels
						lowerCAmelCase__      :		Any    							=      vocab_size
						lowerCAmelCase__      :		str    							=      hidden_size
						lowerCAmelCase__      :		Any    							=      num_hidden_layers
						lowerCAmelCase__      :		str    							=      num_attention_heads
						lowerCAmelCase__      :		Tuple    							=      intermediate_size
						lowerCAmelCase__      :		str    							=      hidden_act
						lowerCAmelCase__      :		Tuple    							=      hidden_dropout_prob
						lowerCAmelCase__      :		Any    							=      attention_probs_dropout_prob
						lowerCAmelCase__      :		int    							=      max_position_embeddings
						lowerCAmelCase__      :		int    							=      type_vocab_size
						lowerCAmelCase__      :		int    							=      type_sequence_label_size
						lowerCAmelCase__      :		List[str]    							=      initializer_range
						lowerCAmelCase__      :		Optional[Any]    							=      num_labels
						lowerCAmelCase__      :		List[Any]    							=      num_choices
						lowerCAmelCase__      :		Optional[int]    							=      scope
						lowerCAmelCase__      :		List[Any]    							=      q_groups
						lowerCAmelCase__      :		Tuple    							=      k_groups
						lowerCAmelCase__      :		Optional[int]    							=      v_groups
						lowerCAmelCase__      :		str    							=      post_attention_groups
						lowerCAmelCase__      :		str    							=      intermediate_groups
						lowerCAmelCase__      :		Optional[int]    							=      output_groups







					def 			__lowerCAmelCase					(			self     :							List[Any]						):
						lowerCAmelCase__      :		Union[str, Any]    							=      ids_tensor([self.batch_size, self.seq_length]  ,self.vocab_size						)

						lowerCAmelCase__      :		Dict    							=      None
						if self.use_input_mask:
							lowerCAmelCase__      :		Tuple    							=      random_attention_mask([self.batch_size, self.seq_length]						)

						lowerCAmelCase__      :		Optional[int]    							=      None
						lowerCAmelCase__      :		Any    							=      None
						lowerCAmelCase__      :		int    							=      None
						if self.use_labels:
							lowerCAmelCase__      :		List[str]    							=      ids_tensor([self.batch_size]  ,self.type_sequence_label_size						)
							lowerCAmelCase__      :		Dict    							=      ids_tensor([self.batch_size, self.seq_length]  ,self.num_labels						)
							lowerCAmelCase__      :		Optional[Any]    							=      ids_tensor([self.batch_size]  ,self.num_choices						)

						lowerCAmelCase__      :		Tuple    							=      self.get_config()

						return config, input_ids, input_mask, sequence_labels, token_labels, choice_labels







					def 			__lowerCAmelCase					(			self     :							Any						):
						return SqueezeBertConfig(
						    embedding_size=self.hidden_size  ,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  ,attention_probs_dropout_prob=self.hidden_dropout_prob  ,attention_dropout=self.attention_probs_dropout_prob  ,max_position_embeddings=self.max_position_embeddings  ,initializer_range=self.initializer_range  ,q_groups=self.q_groups  ,k_groups=self.k_groups  ,v_groups=self.v_groups  ,post_attention_groups=self.post_attention_groups  ,intermediate_groups=self.intermediate_groups  ,output_groups=self.output_groups  ,)







					def 			__lowerCAmelCase					(			self     :							int  ,lowercase_     :							List[str]  ,lowercase_     :							Optional[int]  ,lowercase_     :							List[str]  ,lowercase_     :							int  ,lowercase_     :							Union[str, Any]  ,lowercase_     :							str						):
						lowerCAmelCase__      :		Optional[Any]    							=      SqueezeBertModel(config=lowercase_						)
						model.to(lowercase_						)
						model.eval()
						lowerCAmelCase__      :		List[Any]    							=      model(lowercase_  ,lowercase_						)
						lowerCAmelCase__      :		List[Any]    							=      model(lowercase_						)
						self.parent.assertEqual(result.last_hidden_state.shape  ,(self.batch_size, self.seq_length, self.hidden_size)						)







					def 			__lowerCAmelCase					(			self     :							Union[str, Any]  ,lowercase_     :							str  ,lowercase_     :							str  ,lowercase_     :							Union[str, Any]  ,lowercase_     :							str  ,lowercase_     :							Union[str, Any]  ,lowercase_     :							Optional[int]						):
						lowerCAmelCase__      :		List[Any]    							=      SqueezeBertForMaskedLM(config=lowercase_						)
						model.to(lowercase_						)
						model.eval()
						lowerCAmelCase__      :		str    							=      model(lowercase_  ,attention_mask=lowercase_  ,labels=lowercase_						)
						self.parent.assertEqual(result.logits.shape  ,(self.batch_size, self.seq_length, self.vocab_size)						)







					def 			__lowerCAmelCase					(			self     :							Any  ,lowercase_     :							int  ,lowercase_     :							Union[str, Any]  ,lowercase_     :							str  ,lowercase_     :							Optional[Any]  ,lowercase_     :							Optional[Any]  ,lowercase_     :							Optional[Any]						):
						lowerCAmelCase__      :		str    							=      SqueezeBertForQuestionAnswering(config=lowercase_						)
						model.to(lowercase_						)
						model.eval()
						lowerCAmelCase__      :		str    							=      model(
						    lowercase_  ,attention_mask=lowercase_  ,start_positions=lowercase_  ,end_positions=lowercase_						)
						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 			__lowerCAmelCase					(			self     :							Optional[int]  ,lowercase_     :							Any  ,lowercase_     :							Optional[Any]  ,lowercase_     :							List[Any]  ,lowercase_     :							Tuple  ,lowercase_     :							Union[str, Any]  ,lowercase_     :							List[str]						):
						lowerCAmelCase__      :		List[str]    							=      self.num_labels
						lowerCAmelCase__      :		Union[str, Any]    							=      SqueezeBertForSequenceClassification(lowercase_						)
						model.to(lowercase_						)
						model.eval()
						lowerCAmelCase__      :		List[str]    							=      model(lowercase_  ,attention_mask=lowercase_  ,labels=lowercase_						)
						self.parent.assertEqual(result.logits.shape  ,(self.batch_size, self.num_labels)						)







					def 			__lowerCAmelCase					(			self     :							Tuple  ,lowercase_     :							str  ,lowercase_     :							Optional[Any]  ,lowercase_     :							int  ,lowercase_     :							List[str]  ,lowercase_     :							str  ,lowercase_     :							str						):
						lowerCAmelCase__      :		List[Any]    							=      self.num_labels
						lowerCAmelCase__      :		Optional[int]    							=      SqueezeBertForTokenClassification(config=lowercase_						)
						model.to(lowercase_						)
						model.eval()

						lowerCAmelCase__      :		str    							=      model(lowercase_  ,attention_mask=lowercase_  ,labels=lowercase_						)
						self.parent.assertEqual(result.logits.shape  ,(self.batch_size, self.seq_length, self.num_labels)						)







					def 			__lowerCAmelCase					(			self     :							Union[str, Any]  ,lowercase_     :							Dict  ,lowercase_     :							List[Any]  ,lowercase_     :							Optional[int]  ,lowercase_     :							Optional[int]  ,lowercase_     :							Optional[int]  ,lowercase_     :							List[Any]						):
						lowerCAmelCase__      :		Any    							=      self.num_choices
						lowerCAmelCase__      :		Any    							=      SqueezeBertForMultipleChoice(config=lowercase_						)
						model.to(lowercase_						)
						model.eval()
						lowerCAmelCase__      :		Dict    							=      input_ids.unsqueeze(1						).expand(-1  ,self.num_choices  ,-1						).contiguous()
						lowerCAmelCase__      :		Any    							=      input_mask.unsqueeze(1						).expand(-1  ,self.num_choices  ,-1						).contiguous()
						lowerCAmelCase__      :		List[Any]    							=      model(
						    lowercase_  ,attention_mask=lowercase_  ,labels=lowercase_  ,)
						self.parent.assertEqual(result.logits.shape  ,(self.batch_size, self.num_choices)						)







					def 			__lowerCAmelCase					(			self     :							Optional[int]						):
						lowerCAmelCase__      :		Optional[int]    							=      self.prepare_config_and_inputs()
						((lowerCAmelCase__)							,(lowerCAmelCase__)							,(lowerCAmelCase__)							,(lowerCAmelCase__)							,(lowerCAmelCase__)							,(lowerCAmelCase__))      :		Any    							=      config_and_inputs
						lowerCAmelCase__      :		List[Any]    							=      {'''input_ids''': input_ids, '''attention_mask''': input_mask}
						return config, inputs_dict







@require_torch
class 							SCREAMING_SNAKE_CASE   (						a_       ,				a_       ,				unittest.TestCase			):






					"""simple docstring"""



					lowercase__												=			(
					    (
					        SqueezeBertModel,
					        SqueezeBertForMaskedLM,
					        SqueezeBertForMultipleChoice,
					        SqueezeBertForQuestionAnswering,
					        SqueezeBertForSequenceClassification,
					        SqueezeBertForTokenClassification,
					    )
					    if is_torch_available()
					    else None
					)
					lowercase__												=			(
					    {
					        "feature-extraction": SqueezeBertModel,
					        "fill-mask": SqueezeBertForMaskedLM,
					        "question-answering": SqueezeBertForQuestionAnswering,
					        "text-classification": SqueezeBertForSequenceClassification,
					        "token-classification": SqueezeBertForTokenClassification,
					        "zero-shot": SqueezeBertForSequenceClassification,
					    }
					    if is_torch_available()
					    else {}
					)
					lowercase__												=			False
					lowercase__												=			True
					lowercase__												=			False







					def 			__lowerCAmelCase					(			self     :							List[str]						):
						lowerCAmelCase__      :		Dict    							=      SqueezeBertModelTester(self						)
						lowerCAmelCase__      :		Optional[int]    							=      ConfigTester(self  ,config_class=lowercase_  ,dim=3_7						)







					def 			__lowerCAmelCase					(			self     :							Any						):
						self.config_tester.run_common_tests()







					def 			__lowerCAmelCase					(			self     :							Union[str, Any]						):
						lowerCAmelCase__      :		Dict    							=      self.model_tester.prepare_config_and_inputs()
						self.model_tester.create_and_check_squeezebert_model(*lowercase_						)







					def 			__lowerCAmelCase					(			self     :							int						):
						lowerCAmelCase__      :		Union[str, Any]    							=      self.model_tester.prepare_config_and_inputs()
						self.model_tester.create_and_check_squeezebert_for_masked_lm(*lowercase_						)







					def 			__lowerCAmelCase					(			self     :							str						):
						lowerCAmelCase__      :		Optional[Any]    							=      self.model_tester.prepare_config_and_inputs()
						self.model_tester.create_and_check_squeezebert_for_question_answering(*lowercase_						)







					def 			__lowerCAmelCase					(			self     :							Tuple						):
						lowerCAmelCase__      :		List[str]    							=      self.model_tester.prepare_config_and_inputs()
						self.model_tester.create_and_check_squeezebert_for_sequence_classification(*lowercase_						)







					def 			__lowerCAmelCase					(			self     :							str						):
						lowerCAmelCase__      :		Union[str, Any]    							=      self.model_tester.prepare_config_and_inputs()
						self.model_tester.create_and_check_squeezebert_for_token_classification(*lowercase_						)







					def 			__lowerCAmelCase					(			self     :							List[Any]						):
						lowerCAmelCase__      :		str    							=      self.model_tester.prepare_config_and_inputs()
						self.model_tester.create_and_check_squeezebert_for_multiple_choice(*lowercase_						)







					@slow
					def 			__lowerCAmelCase					(			self     :							Dict						):
						for model_name in SQUEEZEBERT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
							lowerCAmelCase__      :		Union[str, Any]    							=      SqueezeBertModel.from_pretrained(lowercase_						)
							self.assertIsNotNone(lowercase_						)







@require_sentencepiece
@require_tokenizers
@require_torch
class 							SCREAMING_SNAKE_CASE   (						unittest.TestCase			):






					"""simple docstring"""



					@slow
					def 			__lowerCAmelCase					(			self     :							Union[str, Any]						):
						lowerCAmelCase__      :		Union[str, Any]    							=      SqueezeBertForSequenceClassification.from_pretrained('''squeezebert/squeezebert-mnli'''						)

						lowerCAmelCase__      :		Any    							=      torch.tensor([[1, 2_9_4_1_4, 2_3_2, 3_2_8, 7_4_0, 1_1_4_0, 1_2_6_9_5, 6_9, 1_3, 1_5_8_8, 2]]						)
						lowerCAmelCase__      :		Optional[Any]    							=      model(lowercase_						)[0]
						lowerCAmelCase__      :		List[str]    							=      torch.Size((1, 3)						)
						self.assertEqual(output.shape  ,lowercase_						)
						lowerCAmelCase__      :		Optional[Any]    							=      torch.tensor([[0.6401, -0.0349, -0.6041]]						)
						self.assertTrue(torch.allclose(lowercase_  ,lowercase_  ,atol=1E-4						)						)







"""simple docstring"""





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







class 							SCREAMING_SNAKE_CASE   :






					"""simple docstring"""



					def __init__(			self     :							Union[str, Any]						):
						lowerCAmelCase__      :		List[str]    							=      {}







					def 			__lowerCAmelCase					(			self     :							Optional[Any]  ,lowercase_     :							Optional[Any]  ,lowercase_     :							str  ,lowercase_     :							List[str]=1						):
						if self.graph.get(lowercase_						):
							if self.graph[u].count([w, v]						) == 0:
								self.graph[u].append([w, v]						)
						else:
							lowerCAmelCase__      :		Optional[int]    							=      [[w, v]]
						if not self.graph.get(lowercase_						):
							lowerCAmelCase__      :		Union[str, Any]    							=      []







					def 			__lowerCAmelCase					(			self     :							List[Any]						):
						return list(self.graph						)







					def 			__lowerCAmelCase					(			self     :							Dict  ,lowercase_     :							Tuple  ,lowercase_     :							Tuple						):
						if self.graph.get(lowercase_						):
							for _ in self.graph[u]:
								if _[1] == v:
									self.graph[u].remove(lowercase_						)







					def 			__lowerCAmelCase					(			self     :							int  ,lowercase_     :							Any=-2  ,lowercase_     :							List[Any]=-1						):
						if s == d:
							return []
						lowerCAmelCase__      :		int    							=      []
						lowerCAmelCase__      :		List[Any]    							=      []
						if s == -2:
							lowerCAmelCase__      :		int    							=      list(self.graph						)[0]
						stack.append(lowercase_						)
						visited.append(lowercase_						)
						lowerCAmelCase__      :		int    							=      s

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

            # check if all the children are visited
							if s == ss:
								stack.pop()
								if len(lowercase_						) != 0:
									lowerCAmelCase__      :		str    							=      stack[len(lowercase_						) - 1]
							else:
								lowerCAmelCase__      :		Union[str, Any]    							=      ss

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







					def 			__lowerCAmelCase					(			self     :							Dict  ,lowercase_     :							Optional[Any]=-1						):
						if c == -1:
							lowerCAmelCase__      :		Any    							=      floor(random() * 1_0_0_0_0						) + 1_0
						for i in range(lowercase_						):
							# every vertex has max 100 edges
							for _ in range(floor(random() * 1_0_2						) + 1						):
								lowerCAmelCase__      :		Any    							=      floor(random() * c						) + 1
								if n != i:
									self.add_pair(lowercase_  ,lowercase_  ,1						)







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







					def 			__lowerCAmelCase					(			self     :							str  ,lowercase_     :							Optional[int]						):
						return len(self.graph[u]						)







					def 			__lowerCAmelCase					(			self     :							List[str]  ,lowercase_     :							List[str]=-2						):
						lowerCAmelCase__      :		Union[str, Any]    							=      []
						lowerCAmelCase__      :		Any    							=      []
						if s == -2:
							lowerCAmelCase__      :		Any    							=      list(self.graph						)[0]
						stack.append(lowercase_						)
						visited.append(lowercase_						)
						lowerCAmelCase__      :		Tuple    							=      s
						lowerCAmelCase__      :		Optional[int]    							=      []

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

            # check if all the children are visited
							if s == ss:
								sorted_nodes.append(stack.pop()						)
								if len(lowercase_						) != 0:
									lowerCAmelCase__      :		Union[str, Any]    							=      stack[len(lowercase_						) - 1]
							else:
								lowerCAmelCase__      :		int    							=      ss

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







					def 			__lowerCAmelCase					(			self     :							List[Any]						):
						lowerCAmelCase__      :		str    							=      []
						lowerCAmelCase__      :		List[str]    							=      []
						lowerCAmelCase__      :		int    							=      list(self.graph						)[0]
						stack.append(lowercase_						)
						visited.append(lowercase_						)
						lowerCAmelCase__      :		List[Any]    							=      -2
						lowerCAmelCase__      :		str    							=      []
						lowerCAmelCase__      :		Optional[Any]    							=      s
						lowerCAmelCase__      :		Union[str, Any]    							=      False
						lowerCAmelCase__      :		Optional[int]    							=      set()

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

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

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







					def 			__lowerCAmelCase					(			self     :							int						):
						lowerCAmelCase__      :		Tuple    							=      []
						lowerCAmelCase__      :		Tuple    							=      []
						lowerCAmelCase__      :		Any    							=      list(self.graph						)[0]
						stack.append(lowercase_						)
						visited.append(lowercase_						)
						lowerCAmelCase__      :		List[str]    							=      -2
						lowerCAmelCase__      :		int    							=      []
						lowerCAmelCase__      :		int    							=      s
						lowerCAmelCase__      :		List[Any]    							=      False
						lowerCAmelCase__      :		List[str]    							=      set()

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

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

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







					def 			__lowerCAmelCase					(			self     :							Any  ,lowercase_     :							List[Any]=-2  ,lowercase_     :							Union[str, Any]=-1						):
						lowerCAmelCase__      :		Optional[int]    							=      time()
						self.dfs(lowercase_  ,lowercase_						)
						lowerCAmelCase__      :		Any    							=      time()
						return end - begin







					def 			__lowerCAmelCase					(			self     :							Any  ,lowercase_     :							Dict=-2						):
						lowerCAmelCase__      :		List[str]    							=      time()
						self.bfs(lowercase_						)
						lowerCAmelCase__      :		List[Any]    							=      time()
						return end - begin







class 							SCREAMING_SNAKE_CASE   :






					"""simple docstring"""



					def __init__(			self     :							Union[str, Any]						):
						lowerCAmelCase__      :		Tuple    							=      {}







					def 			__lowerCAmelCase					(			self     :							List[Any]  ,lowercase_     :							Optional[int]  ,lowercase_     :							Dict  ,lowercase_     :							Any=1						):
						# check if the u exists
						if self.graph.get(lowercase_						):
							# 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
							lowerCAmelCase__      :		List[Any]    							=      [[w, v]]
						# add the other way
						if self.graph.get(lowercase_						):
							# 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
							lowerCAmelCase__      :		int    							=      [[w, u]]







					def 			__lowerCAmelCase					(			self     :							Dict  ,lowercase_     :							Union[str, Any]  ,lowercase_     :							Dict						):
						if self.graph.get(lowercase_						):
							for _ in self.graph[u]:
								if _[1] == v:
									self.graph[u].remove(lowercase_						)
        # the other way round
						if self.graph.get(lowercase_						):
							for _ in self.graph[v]:
								if _[1] == u:
									self.graph[v].remove(lowercase_						)







					def 			__lowerCAmelCase					(			self     :							int  ,lowercase_     :							Optional[int]=-2  ,lowercase_     :							str=-1						):
						if s == d:
							return []
						lowerCAmelCase__      :		Optional[Any]    							=      []
						lowerCAmelCase__      :		Any    							=      []
						if s == -2:
							lowerCAmelCase__      :		Tuple    							=      list(self.graph						)[0]
						stack.append(lowercase_						)
						visited.append(lowercase_						)
						lowerCAmelCase__      :		int    							=      s

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

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

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







					def 			__lowerCAmelCase					(			self     :							Union[str, Any]  ,lowercase_     :							List[Any]=-1						):
						if c == -1:
							lowerCAmelCase__      :		str    							=      floor(random() * 1_0_0_0_0						) + 1_0
						for i in range(lowercase_						):
							# every vertex has max 100 edges
							for _ in range(floor(random() * 1_0_2						) + 1						):
								lowerCAmelCase__      :		List[str]    							=      floor(random() * c						) + 1
								if n != i:
									self.add_pair(lowercase_  ,lowercase_  ,1						)







					def 			__lowerCAmelCase					(			self     :							Optional[Any]  ,lowercase_     :							List[Any]=-2						):
						lowerCAmelCase__      :		Tuple    							=      deque()
						lowerCAmelCase__      :		List[Any]    							=      []
						if s == -2:
							lowerCAmelCase__      :		Tuple    							=      list(self.graph						)[0]
						d.append(lowercase_						)
						visited.append(lowercase_						)
						while d:
							lowerCAmelCase__      :		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 			__lowerCAmelCase					(			self     :							Any  ,lowercase_     :							Any						):
						return len(self.graph[u]						)







					def 			__lowerCAmelCase					(			self     :							Any						):
						lowerCAmelCase__      :		List[Any]    							=      []
						lowerCAmelCase__      :		int    							=      []
						lowerCAmelCase__      :		List[Any]    							=      list(self.graph						)[0]
						stack.append(lowercase_						)
						visited.append(lowercase_						)
						lowerCAmelCase__      :		Optional[int]    							=      -2
						lowerCAmelCase__      :		List[str]    							=      []
						lowerCAmelCase__      :		Tuple    							=      s
						lowerCAmelCase__      :		Tuple    							=      False
						lowerCAmelCase__      :		Union[str, Any]    							=      set()

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

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

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







					def 			__lowerCAmelCase					(			self     :							Optional[Any]						):
						lowerCAmelCase__      :		Optional[Any]    							=      []
						lowerCAmelCase__      :		Union[str, Any]    							=      []
						lowerCAmelCase__      :		Tuple    							=      list(self.graph						)[0]
						stack.append(lowercase_						)
						visited.append(lowercase_						)
						lowerCAmelCase__      :		Dict    							=      -2
						lowerCAmelCase__      :		Union[str, Any]    							=      []
						lowerCAmelCase__      :		Optional[Any]    							=      s
						lowerCAmelCase__      :		Any    							=      False
						lowerCAmelCase__      :		Optional[int]    							=      set()

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

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

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







					def 			__lowerCAmelCase					(			self     :							str						):
						return list(self.graph						)







					def 			__lowerCAmelCase					(			self     :							Any  ,lowercase_     :							Optional[int]=-2  ,lowercase_     :							Any=-1						):
						lowerCAmelCase__      :		Dict    							=      time()
						self.dfs(lowercase_  ,lowercase_						)
						lowerCAmelCase__      :		List[str]    							=      time()
						return end - begin







					def 			__lowerCAmelCase					(			self     :							Union[str, Any]  ,lowercase_     :							int=-2						):
						lowerCAmelCase__      :		Dict    							=      time()
						self.bfs(lowercase_						)
						lowerCAmelCase__      :		Any    							=      time()
						return end - begin




