




"""simple docstring"""







import unittest

import numpy as np

from transformers.testing_utils import require_torch, require_vision
from transformers.utils import is_torch_available, is_vision_available

from ...test_image_processing_common import ImageProcessingSavingTestMixin


if is_torch_available():
						import torch

if is_vision_available():
						from PIL import Image

						from transformers import ChineseCLIPImageProcessor






class       SCREAMING_SNAKE_CASE__					(					unittest.TestCase					):


						def __init__(							self				:			Tuple						,						lowerCAmelCase				:			Any						,						lowerCAmelCase				:			str=7						,						lowerCAmelCase				:			int=3						,						lowerCAmelCase				:			str=18						,						lowerCAmelCase				:			Any=30						,						lowerCAmelCase				:			Dict=400						,						lowerCAmelCase				:			Tuple=True						,						lowerCAmelCase				:			List[str]=None						,						lowerCAmelCase				:			List[Any]=True						,						lowerCAmelCase				:			Optional[Any]=None						,						lowerCAmelCase				:			Union[str, Any]=True						,						lowerCAmelCase				:			Dict=[0.4814_5466, 0.457_8275, 0.4082_1073]						,						lowerCAmelCase				:			List[Any]=[0.2686_2954, 0.2613_0258, 0.2757_7711]						,						lowerCAmelCase				:			Any=True						,						):
										lowerCAmelCase  =				size if size is not None else {"""height""": 224, """width""": 224}
										lowerCAmelCase  =				crop_size if crop_size is not None else {"""height""": 18, """width""": 18}
										lowerCAmelCase  =				parent
										lowerCAmelCase  =				batch_size
										lowerCAmelCase  =				num_channels
										lowerCAmelCase  =				image_size
										lowerCAmelCase  =				min_resolution
										lowerCAmelCase  =				max_resolution
										lowerCAmelCase  =				do_resize
										lowerCAmelCase  =				size
										lowerCAmelCase  =				do_center_crop
										lowerCAmelCase  =				crop_size
										lowerCAmelCase  =				do_normalize
										lowerCAmelCase  =				image_mean
										lowerCAmelCase  =				image_std
										lowerCAmelCase  =				do_convert_rgb


						def   __lowercase (							self				:			List[str]					):
										return {
										    "do_resize": self.do_resize,
										    "size": self.size,
										    "do_center_crop": self.do_center_crop,
										    "crop_size": self.crop_size,
										    "do_normalize": self.do_normalize,
										    "image_mean": self.image_mean,
										    "image_std": self.image_std,
										    "do_convert_rgb": self.do_convert_rgb,
										}




						def   __lowercase (							self				:			int						,						lowerCAmelCase				:			Any=False						,						lowerCAmelCase				:			Union[str, Any]=False						,						lowerCAmelCase				:			Union[str, Any]=False					):
										assert not (numpify and torchify), "You cannot specify both numpy and PyTorch tensors at the same time"

										if equal_resolution:
														lowerCAmelCase  =				[]
														for i in range(self.batch_size					):
																		image_inputs.append(
																		    np.random.randint(
																		        255						,						size=(self.num_channels, self.max_resolution, self.max_resolution)						,						dtype=np.uinta					)					)
										else:
														lowerCAmelCase  =				[]
														for i in range(self.batch_size					):
																		lowerCAmelCase ,						lowerCAmelCase  =				np.random.choice(np.arange(self.min_resolution						,						self.max_resolution					)						,						2					)
																		image_inputs.append(np.random.randint(255						,						size=(self.num_channels, width, height)						,						dtype=np.uinta					)					)

										if not numpify and not torchify:
														# PIL expects the channel dimension as last dimension
														lowerCAmelCase  =				[Image.fromarray(np.moveaxis(lowerCAmelCase						,						0						,						-1					)					) for x in image_inputs]

										if torchify:
														lowerCAmelCase  =				[torch.from_numpy(lowerCAmelCase					) for x in image_inputs]

										return image_inputs






@require_torch
@require_vision
class       SCREAMING_SNAKE_CASE__					(					_a						,				unittest.TestCase					):
						_a    						=						ChineseCLIPImageProcessor if is_vision_available() else None


						def   __lowercase (							self				:			List[Any]					):
										lowerCAmelCase  =				ChineseCLIPImageProcessingTester(self						,						do_center_crop=lowerCAmelCase					)


						@property
						def   __lowercase (							self				:			Optional[int]					):
										return self.image_processor_tester.prepare_image_processor_dict()


						def   __lowercase (							self				:			Union[str, Any]					):
										lowerCAmelCase  =				self.image_processing_class(**self.image_processor_dict					)
										self.assertTrue(hasattr(lowerCAmelCase						,						"""do_resize"""					)					)
										self.assertTrue(hasattr(lowerCAmelCase						,						"""size"""					)					)
										self.assertTrue(hasattr(lowerCAmelCase						,						"""do_center_crop"""					)					)
										self.assertTrue(hasattr(lowerCAmelCase						,						"""center_crop"""					)					)
										self.assertTrue(hasattr(lowerCAmelCase						,						"""do_normalize"""					)					)
										self.assertTrue(hasattr(lowerCAmelCase						,						"""image_mean"""					)					)
										self.assertTrue(hasattr(lowerCAmelCase						,						"""image_std"""					)					)
										self.assertTrue(hasattr(lowerCAmelCase						,						"""do_convert_rgb"""					)					)


						def   __lowercase (							self				:			Optional[Any]					):
										lowerCAmelCase  =				self.image_processing_class.from_dict(self.image_processor_dict					)
										self.assertEqual(image_processor.size						,						{"""height""": 224, """width""": 224}					)
										self.assertEqual(image_processor.crop_size						,						{"""height""": 18, """width""": 18}					)

										lowerCAmelCase  =				self.image_processing_class.from_dict(self.image_processor_dict						,						size=42						,						crop_size=84					)
										self.assertEqual(image_processor.size						,						{"""shortest_edge""": 42}					)
										self.assertEqual(image_processor.crop_size						,						{"""height""": 84, """width""": 84}					)


						def   __lowercase (							self				:			Dict					):
										pass


						def   __lowercase (							self				:			Union[str, Any]					):
										# Initialize image_processing
										lowerCAmelCase  =				self.image_processing_class(**self.image_processor_dict					)
										# create random PIL images
										lowerCAmelCase  =				self.image_processor_tester.prepare_inputs(equal_resolution=lowerCAmelCase					)
										for image in image_inputs:
														self.assertIsInstance(lowerCAmelCase						,						Image.Image					)

										# Test not batched input
										lowerCAmelCase  =				image_processing(image_inputs[0]						,						return_tensors="""pt"""					).pixel_values
										self.assertEqual(
										    encoded_images.shape						,						(
										        1,
										        self.image_processor_tester.num_channels,
										        self.image_processor_tester.crop_size["""height"""],
										        self.image_processor_tester.crop_size["""width"""],
										    )						,						)

										# Test batched
										lowerCAmelCase  =				image_processing(lowerCAmelCase						,						return_tensors="""pt"""					).pixel_values
										self.assertEqual(
										    encoded_images.shape						,						(
										        self.image_processor_tester.batch_size,
										        self.image_processor_tester.num_channels,
										        self.image_processor_tester.crop_size["""height"""],
										        self.image_processor_tester.crop_size["""width"""],
										    )						,						)


						def   __lowercase (							self				:			List[str]					):
										# Initialize image_processing
										lowerCAmelCase  =				self.image_processing_class(**self.image_processor_dict					)
										# create random numpy tensors
										lowerCAmelCase  =				self.image_processor_tester.prepare_inputs(equal_resolution=lowerCAmelCase						,						numpify=lowerCAmelCase					)
										for image in image_inputs:
														self.assertIsInstance(lowerCAmelCase						,						np.ndarray					)

										# Test not batched input
										lowerCAmelCase  =				image_processing(image_inputs[0]						,						return_tensors="""pt"""					).pixel_values
										self.assertEqual(
										    encoded_images.shape						,						(
										        1,
										        self.image_processor_tester.num_channels,
										        self.image_processor_tester.crop_size["""height"""],
										        self.image_processor_tester.crop_size["""width"""],
										    )						,						)

										# Test batched
										lowerCAmelCase  =				image_processing(lowerCAmelCase						,						return_tensors="""pt"""					).pixel_values
										self.assertEqual(
										    encoded_images.shape						,						(
										        self.image_processor_tester.batch_size,
										        self.image_processor_tester.num_channels,
										        self.image_processor_tester.crop_size["""height"""],
										        self.image_processor_tester.crop_size["""width"""],
										    )						,						)




						def   __lowercase (							self				:			str					):
										# Initialize image_processing
										lowerCAmelCase  =				self.image_processing_class(**self.image_processor_dict					)
										# create random PyTorch tensors
										lowerCAmelCase  =				self.image_processor_tester.prepare_inputs(equal_resolution=lowerCAmelCase						,						torchify=lowerCAmelCase					)
										for image in image_inputs:
														self.assertIsInstance(lowerCAmelCase						,						torch.Tensor					)

										# Test not batched input
										lowerCAmelCase  =				image_processing(image_inputs[0]						,						return_tensors="""pt"""					).pixel_values
										self.assertEqual(
										    encoded_images.shape						,						(
										        1,
										        self.image_processor_tester.num_channels,
										        self.image_processor_tester.crop_size["""height"""],
										        self.image_processor_tester.crop_size["""width"""],
										    )						,						)

										# Test batched
										lowerCAmelCase  =				image_processing(lowerCAmelCase						,						return_tensors="""pt"""					).pixel_values
										self.assertEqual(
										    encoded_images.shape						,						(
										        self.image_processor_tester.batch_size,
										        self.image_processor_tester.num_channels,
										        self.image_processor_tester.crop_size["""height"""],
										        self.image_processor_tester.crop_size["""width"""],
										    )						,						)






@require_torch
@require_vision
class       SCREAMING_SNAKE_CASE__					(					_a						,				unittest.TestCase					):
						_a    						=						ChineseCLIPImageProcessor if is_vision_available() else None


						def   __lowercase (							self				:			Optional[Any]					):
										lowerCAmelCase  =				ChineseCLIPImageProcessingTester(self						,						num_channels=4						,						do_center_crop=lowerCAmelCase					)
										lowerCAmelCase  =				3


						@property
						def   __lowercase (							self				:			Union[str, Any]					):
										return self.image_processor_tester.prepare_image_processor_dict()


						def   __lowercase (							self				:			int					):
										lowerCAmelCase  =				self.image_processing_class(**self.image_processor_dict					)
										self.assertTrue(hasattr(lowerCAmelCase						,						"""do_resize"""					)					)
										self.assertTrue(hasattr(lowerCAmelCase						,						"""size"""					)					)
										self.assertTrue(hasattr(lowerCAmelCase						,						"""do_center_crop"""					)					)
										self.assertTrue(hasattr(lowerCAmelCase						,						"""center_crop"""					)					)
										self.assertTrue(hasattr(lowerCAmelCase						,						"""do_normalize"""					)					)
										self.assertTrue(hasattr(lowerCAmelCase						,						"""image_mean"""					)					)
										self.assertTrue(hasattr(lowerCAmelCase						,						"""image_std"""					)					)
										self.assertTrue(hasattr(lowerCAmelCase						,						"""do_convert_rgb"""					)					)


						def   __lowercase (							self				:			Optional[Any]					):
										pass




						def   __lowercase (							self				:			List[Any]					):
										# Initialize image_processing
										lowerCAmelCase  =				self.image_processing_class(**self.image_processor_dict					)
										# create random PIL images
										lowerCAmelCase  =				self.image_processor_tester.prepare_inputs(equal_resolution=lowerCAmelCase					)
										for image in image_inputs:
														self.assertIsInstance(lowerCAmelCase						,						Image.Image					)

										# Test not batched input
										lowerCAmelCase  =				image_processing(image_inputs[0]						,						return_tensors="""pt"""					).pixel_values
										self.assertEqual(
										    encoded_images.shape						,						(
										        1,
										        self.expected_encoded_image_num_channels,
										        self.image_processor_tester.crop_size["""height"""],
										        self.image_processor_tester.crop_size["""width"""],
										    )						,						)

										# Test batched
										lowerCAmelCase  =				image_processing(lowerCAmelCase						,						return_tensors="""pt"""					).pixel_values
										self.assertEqual(
										    encoded_images.shape						,						(
										        self.image_processor_tester.batch_size,
										        self.expected_encoded_image_num_channels,
										        self.image_processor_tester.crop_size["""height"""],
										        self.image_processor_tester.crop_size["""width"""],
										    )						,						)











"""simple docstring"""







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






class       SCREAMING_SNAKE_CASE__					:


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


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


						def   __lowercase (							self				:			Optional[int]					):
										return list(self.graph					)


						def   __lowercase (							self				:			Optional[Any]						,						lowerCAmelCase				:			Optional[Any]						,						lowerCAmelCase				:			Dict					):
										if self.graph.get(lowerCAmelCase					):
														for _ in self.graph[u]:
																		if _[1] == v:
																						self.graph[u].remove(lowerCAmelCase					)


						def   __lowercase (							self				:			List[str]						,						lowerCAmelCase				:			Tuple=-2						,						lowerCAmelCase				:			List[Any]=-1					):
										if s == d:
														return []
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				[]
										if s == -2:
														lowerCAmelCase  =				list(self.graph					)[0]
										stack.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										lowerCAmelCase  =				s

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

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

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


						def   __lowercase (							self				:			Tuple						,						lowerCAmelCase				:			Any=-1					):
										if c == -1:
														lowerCAmelCase  =				floor(random() * 1_0000					) + 10
										for i in range(lowerCAmelCase					):
														# every vertex has max 100 edges
														for _ in range(floor(random() * 102					) + 1					):
																		lowerCAmelCase  =				floor(random() * c					) + 1
																		if n != i:
																						self.add_pair(lowerCAmelCase						,						lowerCAmelCase						,						1					)


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


						def   __lowercase (							self				:			int						,						lowerCAmelCase				:			Tuple					):
										return len(self.graph[u]					)


						def   __lowercase (							self				:			Optional[int]						,						lowerCAmelCase				:			Optional[Any]=-2					):
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				[]
										if s == -2:
														lowerCAmelCase  =				list(self.graph					)[0]
										stack.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										lowerCAmelCase  =				s
										lowerCAmelCase  =				[]

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

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

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


						def   __lowercase (							self				:			Any					):
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				list(self.graph					)[0]
										stack.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										lowerCAmelCase  =				-2
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				s
										lowerCAmelCase  =				False
										lowerCAmelCase  =				set()

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

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

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


						def   __lowercase (							self				:			Tuple					):
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				list(self.graph					)[0]
										stack.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										lowerCAmelCase  =				-2
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				s
										lowerCAmelCase  =				False
										lowerCAmelCase  =				set()

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

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

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


						def   __lowercase (							self				:			List[Any]						,						lowerCAmelCase				:			Any=-2						,						lowerCAmelCase				:			Tuple=-1					):
										lowerCAmelCase  =				time()
										self.dfs(lowerCAmelCase						,						lowerCAmelCase					)
										lowerCAmelCase  =				time()
										return end - begin




						def   __lowercase (							self				:			int						,						lowerCAmelCase				:			str=-2					):
										lowerCAmelCase  =				time()
										self.bfs(lowerCAmelCase					)
										lowerCAmelCase  =				time()
										return end - begin






class       SCREAMING_SNAKE_CASE__					:


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


						def   __lowercase (							self				:			Optional[Any]						,						lowerCAmelCase				:			Tuple						,						lowerCAmelCase				:			str						,						lowerCAmelCase				:			str=1					):
										# check if the u exists
										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
														lowerCAmelCase  =				[[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
														lowerCAmelCase  =				[[w, u]]


						def   __lowercase (							self				:			Dict						,						lowerCAmelCase				:			Any						,						lowerCAmelCase				:			int					):
										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   __lowercase (							self				:			Dict						,						lowerCAmelCase				:			Optional[int]=-2						,						lowerCAmelCase				:			Optional[Any]=-1					):
										if s == d:
														return []
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				[]
										if s == -2:
														lowerCAmelCase  =				list(self.graph					)[0]
										stack.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										lowerCAmelCase  =				s

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

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

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


						def   __lowercase (							self				:			Any						,						lowerCAmelCase				:			Dict=-1					):
										if c == -1:
														lowerCAmelCase  =				floor(random() * 1_0000					) + 10
										for i in range(lowerCAmelCase					):
														# every vertex has max 100 edges
														for _ in range(floor(random() * 102					) + 1					):
																		lowerCAmelCase  =				floor(random() * c					) + 1
																		if n != i:
																						self.add_pair(lowerCAmelCase						,						lowerCAmelCase						,						1					)


						def   __lowercase (							self				:			int						,						lowerCAmelCase				:			Tuple=-2					):
										lowerCAmelCase  =				deque()
										lowerCAmelCase  =				[]
										if s == -2:
														lowerCAmelCase  =				list(self.graph					)[0]
										d.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										while d:
														lowerCAmelCase  =				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   __lowercase (							self				:			List[str]						,						lowerCAmelCase				:			str					):
										return len(self.graph[u]					)


						def   __lowercase (							self				:			Optional[Any]					):
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				list(self.graph					)[0]
										stack.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										lowerCAmelCase  =				-2
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				s
										lowerCAmelCase  =				False
										lowerCAmelCase  =				set()

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

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

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


						def   __lowercase (							self				:			int					):
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				list(self.graph					)[0]
										stack.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										lowerCAmelCase  =				-2
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				s
										lowerCAmelCase  =				False
										lowerCAmelCase  =				set()

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

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

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


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


						def   __lowercase (							self				:			Dict						,						lowerCAmelCase				:			Dict=-2						,						lowerCAmelCase				:			List[str]=-1					):
										lowerCAmelCase  =				time()
										self.dfs(lowerCAmelCase						,						lowerCAmelCase					)
										lowerCAmelCase  =				time()
										return end - begin




						def   __lowercase (							self				:			str						,						lowerCAmelCase				:			Union[str, Any]=-2					):
										lowerCAmelCase  =				time()
										self.bfs(lowerCAmelCase					)
										lowerCAmelCase  =				time()
										return end - begin





