


'''simple docstring'''


import unittest

from transformers import MODEL_FOR_ZERO_SHOT_OBJECT_DETECTION_MAPPING, is_vision_available, pipeline
from transformers.testing_utils import (
    is_pipeline_test,
    nested_simplify,
    require_tf,
    require_torch,
    require_vision,
    slow,
)

from .test_pipelines_common import ANY


if is_vision_available():
						from PIL import Image
else:






						class 		lowerCAmelCase__	:




									@staticmethod
									def 							lowerCAmelCase__			(						*lowerCamelCase__     :   List[str]		,     **lowerCamelCase__     :   Dict       )      ->str:



											'''simple docstring'''







											pass






@is_pipeline_test
@require_vision
@require_torch
class 		lowerCAmelCase__	(	unittest.TestCase		):
			lowerCAmelCase       :		str				      =   MODEL_FOR_ZERO_SHOT_OBJECT_DETECTION_MAPPING




			def 							lowerCAmelCase__			(						self     :   List[Any]		,     lowerCamelCase__     :   Union[str, Any]		,     lowerCamelCase__     :   Union[str, Any]		,     lowerCamelCase__     :   List[str]       )      ->str:



					'''simple docstring'''







					_UpperCAmelCase						:				Tuple	    =					pipeline(
					    "zero-shot-object-detection"		,     model="hf-internal-testing/tiny-random-owlvit-object-detection"       )

					_UpperCAmelCase						:				Optional[int]	    =					[
					    {
					        "image": "./tests/fixtures/tests_samples/COCO/000000039769.png",
					        "candidate_labels": ["cat", "remote", "couch"],
					    }
					]
					return object_detector, examples




			def 							lowerCAmelCase__			(						self     :   str		,     lowerCamelCase__     :   List[str]		,     lowerCamelCase__     :   Any       )      ->Optional[int]:



					'''simple docstring'''







					_UpperCAmelCase						:				Union[str, Any]	    =					object_detector(examples[0]		,     threshold=0.0       )

					_UpperCAmelCase						:				List[Any]	    =					len(lowerCamelCase__       )
					self.assertGreater(lowerCamelCase__		,     0       )
					self.assertEqual(
					    lowerCamelCase__		,     [
					        {
					            "score": ANY(lowerCamelCase__       ),
					            "label": ANY(lowerCamelCase__       ),
					            "box": {"xmin": ANY(lowerCamelCase__       ), "ymin": ANY(lowerCamelCase__       ), "xmax": ANY(lowerCamelCase__       ), "ymax": ANY(lowerCamelCase__       )},
					        }
					        for i in range(lowerCamelCase__       )
					    ]		,     )




			@require_tf
			@unittest.skip("Zero Shot Object Detection not implemented in TF"       )
			def 							lowerCAmelCase__			(						self     :   Optional[int]       )      ->Tuple:



					'''simple docstring'''







					pass




			@require_torch
			def 							lowerCAmelCase__			(						self     :   Optional[int]       )      ->Dict:



					'''simple docstring'''







					_UpperCAmelCase						:				Optional[int]	    =					pipeline(
					    "zero-shot-object-detection"		,     model="hf-internal-testing/tiny-random-owlvit-object-detection"       )

					_UpperCAmelCase						:				Optional[int]	    =					object_detector(
					    "./tests/fixtures/tests_samples/COCO/000000039769.png"		,     candidate_labels=["cat", "remote", "couch"]		,     threshold=0.6_4		,     )

					self.assertEqual(
					    nested_simplify(lowerCamelCase__		,     decimals=4       )		,     [
					        {"score": 0.7_2_3_5, "label": "cat", "box": {"xmin": 2_04, "ymin": 1_67, "xmax": 2_32, "ymax": 1_90}},
					        {"score": 0.7_2_1_8, "label": "remote", "box": {"xmin": 2_04, "ymin": 1_67, "xmax": 2_32, "ymax": 1_90}},
					        {"score": 0.7_1_8_4, "label": "couch", "box": {"xmin": 2_04, "ymin": 1_67, "xmax": 2_32, "ymax": 1_90}},
					        {"score": 0.6_7_4_8, "label": "remote", "box": {"xmin": 5_71, "ymin": 83, "xmax": 5_98, "ymax": 1_03}},
					        {"score": 0.6_6_5_6, "label": "cat", "box": {"xmin": 5_71, "ymin": 83, "xmax": 5_98, "ymax": 1_03}},
					        {"score": 0.6_6_1_4, "label": "couch", "box": {"xmin": 5_71, "ymin": 83, "xmax": 5_98, "ymax": 1_03}},
					        {"score": 0.6_4_5_6, "label": "remote", "box": {"xmin": 4_94, "ymin": 1_05, "xmax": 5_21, "ymax": 1_27}},
					        {"score": 0.6_4_2, "label": "remote", "box": {"xmin": 67, "ymin": 2_74, "xmax": 93, "ymax": 2_97}},
					        {"score": 0.6_4_1_9, "label": "cat", "box": {"xmin": 4_94, "ymin": 1_05, "xmax": 5_21, "ymax": 1_27}},
					    ]		,     )

					_UpperCAmelCase						:				int	    =					object_detector(
					    [
					        {
					            "image": "./tests/fixtures/tests_samples/COCO/000000039769.png",
					            "candidate_labels": ["cat", "remote", "couch"],
					        }
					    ]		,     threshold=0.6_4		,     )

					self.assertEqual(
					    nested_simplify(lowerCamelCase__		,     decimals=4       )		,     [
					        [
					            {"score": 0.7_2_3_5, "label": "cat", "box": {"xmin": 2_04, "ymin": 1_67, "xmax": 2_32, "ymax": 1_90}},
					            {"score": 0.7_2_1_8, "label": "remote", "box": {"xmin": 2_04, "ymin": 1_67, "xmax": 2_32, "ymax": 1_90}},
					            {"score": 0.7_1_8_4, "label": "couch", "box": {"xmin": 2_04, "ymin": 1_67, "xmax": 2_32, "ymax": 1_90}},
					            {"score": 0.6_7_4_8, "label": "remote", "box": {"xmin": 5_71, "ymin": 83, "xmax": 5_98, "ymax": 1_03}},
					            {"score": 0.6_6_5_6, "label": "cat", "box": {"xmin": 5_71, "ymin": 83, "xmax": 5_98, "ymax": 1_03}},
					            {"score": 0.6_6_1_4, "label": "couch", "box": {"xmin": 5_71, "ymin": 83, "xmax": 5_98, "ymax": 1_03}},
					            {"score": 0.6_4_5_6, "label": "remote", "box": {"xmin": 4_94, "ymin": 1_05, "xmax": 5_21, "ymax": 1_27}},
					            {"score": 0.6_4_2, "label": "remote", "box": {"xmin": 67, "ymin": 2_74, "xmax": 93, "ymax": 2_97}},
					            {"score": 0.6_4_1_9, "label": "cat", "box": {"xmin": 4_94, "ymin": 1_05, "xmax": 5_21, "ymax": 1_27}},
					        ]
					    ]		,     )




			@require_torch
			@slow
			def 							lowerCAmelCase__			(						self     :   int       )      ->List[Any]:



					'''simple docstring'''







					_UpperCAmelCase						:				Any	    =					pipeline("zero-shot-object-detection"       )

					_UpperCAmelCase						:				Dict	    =					object_detector(
					    "http://images.cocodataset.org/val2017/000000039769.jpg"		,     candidate_labels=["cat", "remote", "couch"]		,     )
					self.assertEqual(
					    nested_simplify(lowerCamelCase__		,     decimals=4       )		,     [
					        {"score": 0.2_8_6_8, "label": "cat", "box": {"xmin": 3_24, "ymin": 20, "xmax": 6_40, "ymax": 3_73}},
					        {"score": 0.2_7_7, "label": "remote", "box": {"xmin": 40, "ymin": 72, "xmax": 1_77, "ymax": 1_15}},
					        {"score": 0.2_5_3_7, "label": "cat", "box": {"xmin": 1, "ymin": 55, "xmax": 3_15, "ymax": 4_72}},
					        {"score": 0.1_4_7_4, "label": "remote", "box": {"xmin": 3_35, "ymin": 74, "xmax": 3_71, "ymax": 1_87}},
					        {"score": 0.1_2_0_8, "label": "couch", "box": {"xmin": 4, "ymin": 0, "xmax": 6_42, "ymax": 4_76}},
					    ]		,     )

					_UpperCAmelCase						:				List[str]	    =					object_detector(
					    [
					        {
					            "image": "http://images.cocodataset.org/val2017/000000039769.jpg",
					            "candidate_labels": ["cat", "remote", "couch"],
					        },
					        {
					            "image": "http://images.cocodataset.org/val2017/000000039769.jpg",
					            "candidate_labels": ["cat", "remote", "couch"],
					        },
					    ]		,     )
					self.assertEqual(
					    nested_simplify(lowerCamelCase__		,     decimals=4       )		,     [
					        [
					            {"score": 0.2_8_6_8, "label": "cat", "box": {"xmin": 3_24, "ymin": 20, "xmax": 6_40, "ymax": 3_73}},
					            {"score": 0.2_7_7, "label": "remote", "box": {"xmin": 40, "ymin": 72, "xmax": 1_77, "ymax": 1_15}},
					            {"score": 0.2_5_3_7, "label": "cat", "box": {"xmin": 1, "ymin": 55, "xmax": 3_15, "ymax": 4_72}},
					            {"score": 0.1_4_7_4, "label": "remote", "box": {"xmin": 3_35, "ymin": 74, "xmax": 3_71, "ymax": 1_87}},
					            {"score": 0.1_2_0_8, "label": "couch", "box": {"xmin": 4, "ymin": 0, "xmax": 6_42, "ymax": 4_76}},
					        ],
					        [
					            {"score": 0.2_8_6_8, "label": "cat", "box": {"xmin": 3_24, "ymin": 20, "xmax": 6_40, "ymax": 3_73}},
					            {"score": 0.2_7_7, "label": "remote", "box": {"xmin": 40, "ymin": 72, "xmax": 1_77, "ymax": 1_15}},
					            {"score": 0.2_5_3_7, "label": "cat", "box": {"xmin": 1, "ymin": 55, "xmax": 3_15, "ymax": 4_72}},
					            {"score": 0.1_4_7_4, "label": "remote", "box": {"xmin": 3_35, "ymin": 74, "xmax": 3_71, "ymax": 1_87}},
					            {"score": 0.1_2_0_8, "label": "couch", "box": {"xmin": 4, "ymin": 0, "xmax": 6_42, "ymax": 4_76}},
					        ],
					    ]		,     )




			@require_tf
			@unittest.skip("Zero Shot Object Detection not implemented in TF"       )
			def 							lowerCAmelCase__			(						self     :   Tuple       )      ->Dict:



					'''simple docstring'''







					pass




			@require_torch
			@slow
			def 							lowerCAmelCase__			(						self     :   int       )      ->int:



					'''simple docstring'''







					_UpperCAmelCase						:				Optional[Any]	    =					0.2
					_UpperCAmelCase						:				Dict	    =					pipeline("zero-shot-object-detection"       )

					_UpperCAmelCase						:				Any	    =					object_detector(
					    "http://images.cocodataset.org/val2017/000000039769.jpg"		,     candidate_labels=["cat", "remote", "couch"]		,     threshold=lowerCamelCase__		,     )
					self.assertEqual(
					    nested_simplify(lowerCamelCase__		,     decimals=4       )		,     [
					        {"score": 0.2_8_6_8, "label": "cat", "box": {"xmin": 3_24, "ymin": 20, "xmax": 6_40, "ymax": 3_73}},
					        {"score": 0.2_7_7, "label": "remote", "box": {"xmin": 40, "ymin": 72, "xmax": 1_77, "ymax": 1_15}},
					        {"score": 0.2_5_3_7, "label": "cat", "box": {"xmin": 1, "ymin": 55, "xmax": 3_15, "ymax": 4_72}},
					    ]		,     )






			@require_torch
			@slow
			def 							lowerCAmelCase__			(						self     :   Optional[int]       )      ->str:



					'''simple docstring'''







					_UpperCAmelCase						:				Optional[int]	    =					2
					_UpperCAmelCase						:				str	    =					pipeline("zero-shot-object-detection"       )

					_UpperCAmelCase						:				List[str]	    =					object_detector(
					    "http://images.cocodataset.org/val2017/000000039769.jpg"		,     candidate_labels=["cat", "remote", "couch"]		,     top_k=lowerCamelCase__		,     )
					self.assertEqual(
					    nested_simplify(lowerCamelCase__		,     decimals=4       )		,     [
					        {"score": 0.2_8_6_8, "label": "cat", "box": {"xmin": 3_24, "ymin": 20, "xmax": 6_40, "ymax": 3_73}},
					        {"score": 0.2_7_7, "label": "remote", "box": {"xmin": 40, "ymin": 72, "xmax": 1_77, "ymax": 1_15}},
					    ]		,     )







'''simple docstring'''


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






class 		lowerCAmelCase__	:




			def __init__(						self     :   Union[str, Any]       )      ->Union[str, Any]:



					'''simple docstring'''







					_UpperCAmelCase						:				List[Any]	    =					{}




			def 							lowerCAmelCase__			(						self     :   Dict		,     lowerCamelCase__     :   Tuple		,     lowerCamelCase__     :   List[str]		,     lowerCamelCase__     :   int=1       )      ->Optional[Any]:



					'''simple docstring'''







					if self.graph.get(lowerCamelCase__       ):
							if self.graph[u].count([w, v]       ) == 0:
									self.graph[u].append([w, v]       )
					else:
							_UpperCAmelCase						:				Dict	    =					[[w, v]]
					if not self.graph.get(lowerCamelCase__       ):
							_UpperCAmelCase						:				str	    =					[]




			def 							lowerCAmelCase__			(						self     :   Any       )      ->Tuple:



					'''simple docstring'''







					return list(self.graph       )




			def 							lowerCAmelCase__			(						self     :   Tuple		,     lowerCamelCase__     :   Union[str, Any]		,     lowerCamelCase__     :   str       )      ->Any:



					'''simple docstring'''







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




			def 							lowerCAmelCase__			(						self     :   int		,     lowerCamelCase__     :   Optional[Any]=-2		,     lowerCamelCase__     :   Optional[int]=-1       )      ->int:



					'''simple docstring'''







					if s == d:
							return []
					_UpperCAmelCase						:				Tuple	    =					[]
					_UpperCAmelCase						:				Optional[int]	    =					[]
					if s == -2:
							_UpperCAmelCase						:				Union[str, Any]	    =					list(self.graph       )[0]
					stack.append(lowerCamelCase__       )
					visited.append(lowerCamelCase__       )
					_UpperCAmelCase						:				Optional[Any]	    =					s

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

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

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




			def 							lowerCAmelCase__			(						self     :   List[Any]		,     lowerCamelCase__     :   Any=-1       )      ->str:



					'''simple docstring'''







					if c == -1:
							_UpperCAmelCase						:				str	    =					floor(random() * 1_00_00       ) + 10
					for i in range(lowerCamelCase__       ):
							# every vertex has max 100 edges
							for _ in range(floor(random() * 1_02       ) + 1       ):
									_UpperCAmelCase						:				Tuple	    =					floor(random() * c       ) + 1
									if n != i:
											self.add_pair(lowerCamelCase__		,     lowerCamelCase__		,     1       )




			def 							lowerCAmelCase__			(						self     :   Any		,     lowerCamelCase__     :   Union[str, Any]=-2       )      ->Union[str, Any]:



					'''simple docstring'''







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



					'''simple docstring'''







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




			def 							lowerCAmelCase__			(						self     :   int		,     lowerCamelCase__     :   Union[str, Any]       )      ->int:



					'''simple docstring'''







					return len(self.graph[u]       )




			def 							lowerCAmelCase__			(						self     :   int		,     lowerCamelCase__     :   Any=-2       )      ->int:



					'''simple docstring'''







					_UpperCAmelCase						:				Optional[Any]	    =					[]
					_UpperCAmelCase						:				List[str]	    =					[]
					if s == -2:
							_UpperCAmelCase						:				str	    =					list(self.graph       )[0]
					stack.append(lowerCamelCase__       )
					visited.append(lowerCamelCase__       )
					_UpperCAmelCase						:				List[Any]	    =					s
					_UpperCAmelCase						:				Tuple	    =					[]

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

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

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




			def 							lowerCAmelCase__			(						self     :   Union[str, Any]       )      ->Optional[Any]:



					'''simple docstring'''







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

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

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

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




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



					'''simple docstring'''







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

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

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

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




			def 							lowerCAmelCase__			(						self     :   str		,     lowerCamelCase__     :   Tuple=-2		,     lowerCamelCase__     :   Union[str, Any]=-1       )      ->Any:



					'''simple docstring'''







					_UpperCAmelCase						:				Dict	    =					time()
					self.dfs(lowerCamelCase__		,     lowerCamelCase__       )
					_UpperCAmelCase						:				Tuple	    =					time()
					return end - begin






			def 							lowerCAmelCase__			(						self     :   List[Any]		,     lowerCamelCase__     :   Dict=-2       )      ->Union[str, Any]:



					'''simple docstring'''







					_UpperCAmelCase						:				Optional[Any]	    =					time()
					self.bfs(lowerCamelCase__       )
					_UpperCAmelCase						:				Tuple	    =					time()
					return end - begin






class 		lowerCAmelCase__	:




			def __init__(						self     :   Tuple       )      ->int:



					'''simple docstring'''







					_UpperCAmelCase						:				Any	    =					{}




			def 							lowerCAmelCase__			(						self     :   int		,     lowerCamelCase__     :   List[str]		,     lowerCamelCase__     :   str		,     lowerCamelCase__     :   Tuple=1       )      ->int:



					'''simple docstring'''







					if self.graph.get(lowerCamelCase__       ):
							# 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
							_UpperCAmelCase						:				Dict	    =					[[w, v]]
					# add the other way
					if self.graph.get(lowerCamelCase__       ):
							# 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
							_UpperCAmelCase						:				Tuple	    =					[[w, u]]




			def 							lowerCAmelCase__			(						self     :   Dict		,     lowerCamelCase__     :   Any		,     lowerCamelCase__     :   Optional[Any]       )      ->Dict:



					'''simple docstring'''







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




			def 							lowerCAmelCase__			(						self     :   List[str]		,     lowerCamelCase__     :   List[str]=-2		,     lowerCamelCase__     :   List[str]=-1       )      ->List[Any]:



					'''simple docstring'''







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

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

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

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




			def 							lowerCAmelCase__			(						self     :   Any		,     lowerCamelCase__     :   Dict=-1       )      ->str:



					'''simple docstring'''







					if c == -1:
							_UpperCAmelCase						:				str	    =					floor(random() * 1_00_00       ) + 10
					for i in range(lowerCamelCase__       ):
							# every vertex has max 100 edges
							for _ in range(floor(random() * 1_02       ) + 1       ):
									_UpperCAmelCase						:				str	    =					floor(random() * c       ) + 1
									if n != i:
											self.add_pair(lowerCamelCase__		,     lowerCamelCase__		,     1       )




			def 							lowerCAmelCase__			(						self     :   str		,     lowerCamelCase__     :   Union[str, Any]=-2       )      ->Any:



					'''simple docstring'''







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



					'''simple docstring'''







					return len(self.graph[u]       )




			def 							lowerCAmelCase__			(						self     :   str       )      ->Any:



					'''simple docstring'''







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

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

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

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




			def 							lowerCAmelCase__			(						self     :   Optional[Any]       )      ->Dict:



					'''simple docstring'''







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

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

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

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




			def 							lowerCAmelCase__			(						self     :   Optional[Any]       )      ->int:



					'''simple docstring'''







					return list(self.graph       )




			def 							lowerCAmelCase__			(						self     :   int		,     lowerCamelCase__     :   Dict=-2		,     lowerCamelCase__     :   Dict=-1       )      ->List[Any]:



					'''simple docstring'''







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






			def 							lowerCAmelCase__			(						self     :   int		,     lowerCamelCase__     :   Any=-2       )      ->int:



					'''simple docstring'''







					_UpperCAmelCase						:				Optional[Any]	    =					time()
					self.bfs(lowerCamelCase__       )
					_UpperCAmelCase						:				Any	    =					time()
					return end - begin



