




'''simple docstring'''


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

class      A       :







							def __init__(    self			:    Tuple   )     ->				str:


														"""simple docstring"""


														_a      	=							{}







							def   __lowerCAmelCase     (    self			:    Dict				,     lowerCAmelCase_			:    Tuple				,     lowerCAmelCase_			:    List[Any]				,     lowerCAmelCase_			:    List[Any]=1   )     ->				Dict:


														"""simple docstring"""


														if self.graph.get(lowerCAmelCase_   ):
																					if self.graph[u].count([w, v]   ) == 0:
																												self.graph[u].append([w, v]   )
														else:
																					_a      	=							[[w, v]]
														if not self.graph.get(lowerCAmelCase_   ):
																					_a      	=							[]







							def   __lowerCAmelCase     (    self			:    List[str]   )     ->				Dict:


														"""simple docstring"""


														return list(self.graph   )







							def   __lowerCAmelCase     (    self			:    Optional[int]				,     lowerCAmelCase_			:    List[Any]				,     lowerCAmelCase_			:    List[Any]   )     ->				str:


														"""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_			:    Dict=-2				,     lowerCAmelCase_			:    List[str]=-1   )     ->				Union[str, Any]:


														"""simple docstring"""


														if s == d:
																					return []
														_a      	=							[]
														_a      	=							[]
														if s == -2:
																					_a      	=							list(self.graph   )[0]
														stack.append(lowerCAmelCase_   )
														visited.append(lowerCAmelCase_   )
														_a      	=							s

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

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

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







							def   __lowerCAmelCase     (    self			:    str				,     lowerCAmelCase_			:    Optional[int]=-1   )     ->				str:


														"""simple docstring"""


														if c == -1:
																					_a      	=							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   ):
																												_a      	=							floor(random() * c   ) + 1
																												if n != i:
																																			self.add_pair(lowerCAmelCase_				,     lowerCAmelCase_				,     1   )







							def   __lowerCAmelCase     (    self			:    List[str]				,     lowerCAmelCase_			:    Dict=-2   )     ->				Optional[int]:


														"""simple docstring"""


														_a      	=							deque()
														_a      	=							[]
														if s == -2:
																					_a      	=							list(self.graph   )[0]
														d.append(lowerCAmelCase_   )
														visited.append(lowerCAmelCase_   )
														while d:
																					_a      	=							d.popleft()
																					if len(self.graph[s]   ) != 0:
																												for node in self.graph[s]:
																																			if visited.count(node[1]   ) < 1:
																																										d.append(node[1]   )
																																										visited.append(node[1]   )
														return visited







							def   __lowerCAmelCase     (    self			:    int				,     lowerCAmelCase_			:    Dict   )     ->				List[Any]:


														"""simple docstring"""


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







							def   __lowerCAmelCase     (    self			:    Tuple				,     lowerCAmelCase_			:    List[Any]   )     ->				Dict:


														"""simple docstring"""


														return len(self.graph[u]   )







							def   __lowerCAmelCase     (    self			:    str				,     lowerCAmelCase_			:    List[str]=-2   )     ->				int:


														"""simple docstring"""


														_a      	=							[]
														_a      	=							[]
														if s == -2:
																					_a      	=							list(self.graph   )[0]
														stack.append(lowerCAmelCase_   )
														visited.append(lowerCAmelCase_   )
														_a      	=							s
														_a      	=							[]

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

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

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







							def   __lowerCAmelCase     (    self			:    List[Any]   )     ->				int:


														"""simple docstring"""


														_a      	=							[]
														_a      	=							[]
														_a      	=							list(self.graph   )[0]
														stack.append(lowerCAmelCase_   )
														visited.append(lowerCAmelCase_   )
														_a      	=							-2
														_a      	=							[]
														_a      	=							s
														_a      	=							False
														_a      	=							set()

														while True:
																					# check if there is any non isolated nodes
																					if len(self.graph[s]   ) != 0:
																												_a      	=							s
																												for node in self.graph[s]:
																																			if (
																																			    visited.count(node[1]   ) > 0
																																			    and node[1] != parent
																																			    and indirect_parents.count(node[1]   ) > 0
																																			    and not on_the_way_back
																																			):
																																										_a      	=							len(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]   )
																																										_a      	=							node[1]
																																										break

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

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







							def   __lowerCAmelCase     (    self			:    Optional[Any]   )     ->				List[Any]:


														"""simple docstring"""


														_a      	=							[]
														_a      	=							[]
														_a      	=							list(self.graph   )[0]
														stack.append(lowerCAmelCase_   )
														visited.append(lowerCAmelCase_   )
														_a      	=							-2
														_a      	=							[]
														_a      	=							s
														_a      	=							False
														_a      	=							set()

														while True:
																					# check if there is any non isolated nodes
																					if len(self.graph[s]   ) != 0:
																												_a      	=							s
																												for node in self.graph[s]:
																																			if (
																																			    visited.count(node[1]   ) > 0
																																			    and node[1] != parent
																																			    and indirect_parents.count(node[1]   ) > 0
																																			    and not on_the_way_back
																																			):
																																										_a      	=							len(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]   )
																																										_a      	=							node[1]
																																										break

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

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







							def   __lowerCAmelCase     (    self			:    Optional[Any]				,     lowerCAmelCase_			:    Any=-2				,     lowerCAmelCase_			:    Optional[Any]=-1   )     ->				Optional[Any]:


														"""simple docstring"""


														_a      	=							time()
														self.dfs(lowerCAmelCase_				,     lowerCAmelCase_   )
														_a      	=							time()
														return end - begin







							def   __lowerCAmelCase     (    self			:    Tuple				,     lowerCAmelCase_			:    Tuple=-2   )     ->				List[str]:


														"""simple docstring"""


														_a      	=							time()
														self.bfs(lowerCAmelCase_   )
														_a      	=							time()
														return end - begin



class      A       :







							def __init__(    self			:    List[Any]   )     ->				Any:


														"""simple docstring"""


														_a      	=							{}







							def   __lowerCAmelCase     (    self			:    Tuple				,     lowerCAmelCase_			:    Optional[Any]				,     lowerCAmelCase_			:    Tuple				,     lowerCAmelCase_			:    str=1   )     ->				Dict:


														"""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
																					_a      	=							[[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
																					_a      	=							[[w, u]]







							def   __lowerCAmelCase     (    self			:    int				,     lowerCAmelCase_			:    Tuple				,     lowerCAmelCase_			:    Tuple   )     ->				int:


														"""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			:    Any				,     lowerCAmelCase_			:    Any=-2				,     lowerCAmelCase_			:    Optional[int]=-1   )     ->				Optional[int]:


														"""simple docstring"""


														if s == d:
																					return []
														_a      	=							[]
														_a      	=							[]
														if s == -2:
																					_a      	=							list(self.graph   )[0]
														stack.append(lowerCAmelCase_   )
														visited.append(lowerCAmelCase_   )
														_a      	=							s

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

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

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







							def   __lowerCAmelCase     (    self			:    int				,     lowerCAmelCase_			:    Union[str, Any]=-1   )     ->				Any:


														"""simple docstring"""


														if c == -1:
																					_a      	=							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   ):
																												_a      	=							floor(random() * c   ) + 1
																												if n != i:
																																			self.add_pair(lowerCAmelCase_				,     lowerCAmelCase_				,     1   )







							def   __lowerCAmelCase     (    self			:    str				,     lowerCAmelCase_			:    List[Any]=-2   )     ->				Optional[Any]:


														"""simple docstring"""


														_a      	=							deque()
														_a      	=							[]
														if s == -2:
																					_a      	=							list(self.graph   )[0]
														d.append(lowerCAmelCase_   )
														visited.append(lowerCAmelCase_   )
														while d:
																					_a      	=							d.popleft()
																					if len(self.graph[s]   ) != 0:
																												for node in self.graph[s]:
																																			if visited.count(node[1]   ) < 1:
																																										d.append(node[1]   )
																																										visited.append(node[1]   )
														return visited







							def   __lowerCAmelCase     (    self			:    Tuple				,     lowerCAmelCase_			:    Optional[int]   )     ->				Any:


														"""simple docstring"""


														return len(self.graph[u]   )







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


														"""simple docstring"""


														_a      	=							[]
														_a      	=							[]
														_a      	=							list(self.graph   )[0]
														stack.append(lowerCAmelCase_   )
														visited.append(lowerCAmelCase_   )
														_a      	=							-2
														_a      	=							[]
														_a      	=							s
														_a      	=							False
														_a      	=							set()

														while True:
																					# check if there is any non isolated nodes
																					if len(self.graph[s]   ) != 0:
																												_a      	=							s
																												for node in self.graph[s]:
																																			if (
																																			    visited.count(node[1]   ) > 0
																																			    and node[1] != parent
																																			    and indirect_parents.count(node[1]   ) > 0
																																			    and not on_the_way_back
																																			):
																																										_a      	=							len(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]   )
																																										_a      	=							node[1]
																																										break

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

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







							def   __lowerCAmelCase     (    self			:    str   )     ->				str:


														"""simple docstring"""


														_a      	=							[]
														_a      	=							[]
														_a      	=							list(self.graph   )[0]
														stack.append(lowerCAmelCase_   )
														visited.append(lowerCAmelCase_   )
														_a      	=							-2
														_a      	=							[]
														_a      	=							s
														_a      	=							False
														_a      	=							set()

														while True:
																					# check if there is any non isolated nodes
																					if len(self.graph[s]   ) != 0:
																												_a      	=							s
																												for node in self.graph[s]:
																																			if (
																																			    visited.count(node[1]   ) > 0
																																			    and node[1] != parent
																																			    and indirect_parents.count(node[1]   ) > 0
																																			    and not on_the_way_back
																																			):
																																										_a      	=							len(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]   )
																																										_a      	=							node[1]
																																										break

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

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







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


														"""simple docstring"""


														return list(self.graph   )







							def   __lowerCAmelCase     (    self			:    Tuple				,     lowerCAmelCase_			:    int=-2				,     lowerCAmelCase_			:    int=-1   )     ->				List[Any]:


														"""simple docstring"""


														_a      	=							time()
														self.dfs(lowerCAmelCase_				,     lowerCAmelCase_   )
														_a      	=							time()
														return end - begin







							def   __lowerCAmelCase     (    self			:    Union[str, Any]				,     lowerCAmelCase_			:    Dict=-2   )     ->				int:


														"""simple docstring"""


														_a      	=							time()
														self.bfs(lowerCAmelCase_   )
														_a      	=							time()
														return end - begin







'''simple docstring'''


import PIL.Image
import PIL.ImageOps
from packaging import version
from PIL import Image


if version.parse(version.parse(PIL.__version__).base_version) >= version.parse('9.1.0'):
				_snake_case : Tuple  				=						{
				    'linear': PIL.Image.Resampling.BILINEAR,
				    'bilinear': PIL.Image.Resampling.BILINEAR,
				    'bicubic': PIL.Image.Resampling.BICUBIC,
				    'lanczos': PIL.Image.Resampling.LANCZOS,
				    'nearest': PIL.Image.Resampling.NEAREST,
				}
else:
				_snake_case : Any  				=						{
				    'linear': PIL.Image.LINEAR,
				    'bilinear': PIL.Image.BILINEAR,
				    'bicubic': PIL.Image.BICUBIC,
				    'lanczos': PIL.Image.LANCZOS,
				    'nearest': PIL.Image.NEAREST,
				}
def 						snake_case_       (UpperCamelCase			:    Optional[int] ):





							'''simple docstring'''


							_a      	=							(images / 2 + 0.5).clamp(0					,		1 )
							_a      	=							images.cpu().permute(0					,		2					,		3					,		1 ).float().numpy()
							_a      	=							numpy_to_pil(UpperCamelCase )
							return images

def 						snake_case_       (UpperCamelCase			:    str ):





							'''simple docstring'''


							if images.ndim == 3:
														_a      	=							images[None, ...]
							_a      	=							(images * 255).round().astype('''uint8''' )
							if images.shape[-1] == 1:
														# special case for grayscale (single channel) images
														_a      	=							[Image.fromarray(image.squeeze()					,		mode='''L''' ) for image in images]
							else:
														_a      	=							[Image.fromarray(UpperCamelCase ) for image in images]

							return pil_images

