



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



class     UpperCAmelCase_       :







							def __init__(  self):

														'''simple docstring'''

														_lowerCAmelCase	:				Dict					  =       {}







							def   snake_case__ (  self,     __a,     __a,     __a=1):

														'''simple docstring'''

														if self.graph.get(__a):
																					if self.graph[u].count([w, v]) == 0:
																												self.graph[u].append([w, v])
														else:
																					_lowerCAmelCase	:				Union[str, Any]					  =       [[w, v]]
														if not self.graph.get(__a):
																					_lowerCAmelCase	:				Optional[Any]					  =       []







							def   snake_case__ (  self):

														'''simple docstring'''

														return list(self.graph)







							def   snake_case__ (  self,     __a,     __a):

														'''simple docstring'''

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







							def   snake_case__ (  self,     __a=-2,     __a=-1):

														'''simple docstring'''

														if s == d:
																					return []
														_lowerCAmelCase	:				Optional[Any]					  =       []
														_lowerCAmelCase	:				List[str]					  =       []
														if s == -2:
																					_lowerCAmelCase	:				List[Any]					  =       list(self.graph)[0]
														stack.append(__a)
														visited.append(__a)
														_lowerCAmelCase	:				Optional[int]					  =       s

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

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

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







							def   snake_case__ (  self,     __a=-1):

														'''simple docstring'''

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







							def   snake_case__ (  self,     __a=-2):

														'''simple docstring'''

														_lowerCAmelCase	:				Any					  =       deque()
														_lowerCAmelCase	:				Optional[Any]					  =       []
														if s == -2:
																					_lowerCAmelCase	:				Optional[int]					  =       list(self.graph)[0]
														d.append(__a)
														visited.append(__a)
														while d:
																					_lowerCAmelCase	:				Optional[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   snake_case__ (  self,     __a):

														'''simple docstring'''

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







							def   snake_case__ (  self,     __a):

														'''simple docstring'''

														return len(self.graph[u])







							def   snake_case__ (  self,     __a=-2):

														'''simple docstring'''

														_lowerCAmelCase	:				List[str]					  =       []
														_lowerCAmelCase	:				Optional[int]					  =       []
														if s == -2:
																					_lowerCAmelCase	:				Dict					  =       list(self.graph)[0]
														stack.append(__a)
														visited.append(__a)
														_lowerCAmelCase	:				List[Any]					  =       s
														_lowerCAmelCase	:				Optional[int]					  =       []

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

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

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







							def   snake_case__ (  self):

														'''simple docstring'''

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

														while True:
																					# check if there is any non isolated nodes
																					if len(self.graph[s]) != 0:
																												_lowerCAmelCase	:				Dict					  =       s
																												for node in self.graph[s]:
																																			if (
																																			    visited.count(node[1]) > 0
																																			    and node[1] != parent
																																			    and indirect_parents.count(node[1]) > 0
																																			    and not on_the_way_back
																																			):
																																										_lowerCAmelCase	:				Tuple					  =       len(__a) - 1
																																										while len_stack >= 0:
																																																	if stack[len_stack] == node[1]:
																																																								anticipating_nodes.add(node[1])
																																																								break
																																																	else:
																																																								anticipating_nodes.add(stack[len_stack])
																																																								len_stack -= 1
																																			if visited.count(node[1]) < 1:
																																										stack.append(node[1])
																																										visited.append(node[1])
																																										_lowerCAmelCase	:				int					  =       node[1]
																																										break

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

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







							def   snake_case__ (  self):

														'''simple docstring'''

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

														while True:
																					# check if there is any non isolated nodes
																					if len(self.graph[s]) != 0:
																												_lowerCAmelCase	:				Dict					  =       s
																												for node in self.graph[s]:
																																			if (
																																			    visited.count(node[1]) > 0
																																			    and node[1] != parent
																																			    and indirect_parents.count(node[1]) > 0
																																			    and not on_the_way_back
																																			):
																																										_lowerCAmelCase	:				List[str]					  =       len(__a) - 1
																																										while len_stack_minus_one >= 0:
																																																	if stack[len_stack_minus_one] == node[1]:
																																																								anticipating_nodes.add(node[1])
																																																								break
																																																	else:
																																																								return True
																																			if visited.count(node[1]) < 1:
																																										stack.append(node[1])
																																										visited.append(node[1])
																																										_lowerCAmelCase	:				List[Any]					  =       node[1]
																																										break

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

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







							def   snake_case__ (  self,     __a=-2,     __a=-1):

														'''simple docstring'''

														_lowerCAmelCase	:				Union[str, Any]					  =       time()
														self.dfs(__a,     __a)
														_lowerCAmelCase	:				str					  =       time()
														return end - begin







							def   snake_case__ (  self,     __a=-2):

														'''simple docstring'''

														_lowerCAmelCase	:				List[Any]					  =       time()
														self.bfs(__a)
														_lowerCAmelCase	:				int					  =       time()
														return end - begin



class     UpperCAmelCase_       :







							def __init__(  self):

														'''simple docstring'''

														_lowerCAmelCase	:				str					  =       {}







							def   snake_case__ (  self,     __a,     __a,     __a=1):

														'''simple docstring'''

														if self.graph.get(__a):
																					# if there already is a edge
																					if self.graph[u].count([w, v]) == 0:
																												self.graph[u].append([w, v])
														else:
																					# if u does not exist
																					_lowerCAmelCase	:				str					  =       [[w, v]]
														# add the other way
														if self.graph.get(__a):
																					# if there already is a edge
																					if self.graph[v].count([w, u]) == 0:
																												self.graph[v].append([w, u])
														else:
																					# if u does not exist
																					_lowerCAmelCase	:				Union[str, Any]					  =       [[w, u]]







							def   snake_case__ (  self,     __a,     __a):

														'''simple docstring'''

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







							def   snake_case__ (  self,     __a=-2,     __a=-1):

														'''simple docstring'''

														if s == d:
																					return []
														_lowerCAmelCase	:				int					  =       []
														_lowerCAmelCase	:				Tuple					  =       []
														if s == -2:
																					_lowerCAmelCase	:				int					  =       list(self.graph)[0]
														stack.append(__a)
														visited.append(__a)
														_lowerCAmelCase	:				str					  =       s

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

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

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







							def   snake_case__ (  self,     __a=-1):

														'''simple docstring'''

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







							def   snake_case__ (  self,     __a=-2):

														'''simple docstring'''

														_lowerCAmelCase	:				str					  =       deque()
														_lowerCAmelCase	:				Any					  =       []
														if s == -2:
																					_lowerCAmelCase	:				List[str]					  =       list(self.graph)[0]
														d.append(__a)
														visited.append(__a)
														while d:
																					_lowerCAmelCase	:				Tuple					  =       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   snake_case__ (  self,     __a):

														'''simple docstring'''

														return len(self.graph[u])







							def   snake_case__ (  self):

														'''simple docstring'''

														_lowerCAmelCase	:				List[str]					  =       []
														_lowerCAmelCase	:				Optional[Any]					  =       []
														_lowerCAmelCase	:				List[Any]					  =       list(self.graph)[0]
														stack.append(__a)
														visited.append(__a)
														_lowerCAmelCase	:				int					  =       -2
														_lowerCAmelCase	:				Tuple					  =       []
														_lowerCAmelCase	:				Dict					  =       s
														_lowerCAmelCase	:				Dict					  =       False
														_lowerCAmelCase	:				Optional[Any]					  =       set()

														while True:
																					# check if there is any non isolated nodes
																					if len(self.graph[s]) != 0:
																												_lowerCAmelCase	:				Dict					  =       s
																												for node in self.graph[s]:
																																			if (
																																			    visited.count(node[1]) > 0
																																			    and node[1] != parent
																																			    and indirect_parents.count(node[1]) > 0
																																			    and not on_the_way_back
																																			):
																																										_lowerCAmelCase	:				List[str]					  =       len(__a) - 1
																																										while len_stack >= 0:
																																																	if stack[len_stack] == node[1]:
																																																								anticipating_nodes.add(node[1])
																																																								break
																																																	else:
																																																								anticipating_nodes.add(stack[len_stack])
																																																								len_stack -= 1
																																			if visited.count(node[1]) < 1:
																																										stack.append(node[1])
																																										visited.append(node[1])
																																										_lowerCAmelCase	:				List[Any]					  =       node[1]
																																										break

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

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







							def   snake_case__ (  self):

														'''simple docstring'''

														_lowerCAmelCase	:				Dict					  =       []
														_lowerCAmelCase	:				Optional[Any]					  =       []
														_lowerCAmelCase	:				str					  =       list(self.graph)[0]
														stack.append(__a)
														visited.append(__a)
														_lowerCAmelCase	:				List[Any]					  =       -2
														_lowerCAmelCase	:				str					  =       []
														_lowerCAmelCase	:				Any					  =       s
														_lowerCAmelCase	:				str					  =       False
														_lowerCAmelCase	:				Optional[Any]					  =       set()

														while True:
																					# check if there is any non isolated nodes
																					if len(self.graph[s]) != 0:
																												_lowerCAmelCase	:				int					  =       s
																												for node in self.graph[s]:
																																			if (
																																			    visited.count(node[1]) > 0
																																			    and node[1] != parent
																																			    and indirect_parents.count(node[1]) > 0
																																			    and not on_the_way_back
																																			):
																																										_lowerCAmelCase	:				Optional[Any]					  =       len(__a) - 1
																																										while len_stack_minus_one >= 0:
																																																	if stack[len_stack_minus_one] == node[1]:
																																																								anticipating_nodes.add(node[1])
																																																								break
																																																	else:
																																																								return True
																																			if visited.count(node[1]) < 1:
																																										stack.append(node[1])
																																										visited.append(node[1])
																																										_lowerCAmelCase	:				int					  =       node[1]
																																										break

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

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







							def   snake_case__ (  self):

														'''simple docstring'''

														return list(self.graph)







							def   snake_case__ (  self,     __a=-2,     __a=-1):

														'''simple docstring'''

														_lowerCAmelCase	:				str					  =       time()
														self.dfs(__a,     __a)
														_lowerCAmelCase	:				str					  =       time()
														return end - begin







							def   snake_case__ (  self,     __a=-2):

														'''simple docstring'''

														_lowerCAmelCase	:				Optional[Any]					  =       time()
														self.bfs(__a)
														_lowerCAmelCase	:				List[Any]					  =       time()
														return end - begin






'''simple docstring'''


from multiprocessing import Lock, Pipe, Process

# lock used to ensure that two processes do not access a pipe at the same time
UpperCAmelCase_					=   Lock()


def     SCREAMING_SNAKE_CASE							(   a_						:				str					,       a_						:				Tuple					,       a_						:				Dict					,       a_						:				Optional[Any]					,       a_						:				str					,       a_						:				Any					,       a_						:				Optional[Any]      ):
  global process_lock

  # we perform n swaps since after n swaps we know we are sorted
  # we *could* stop early if we are sorted already, but it takes as long to
  # find out we are sorted as it does to sort the list with this algorithm
  for i in range(0					,       10      ):
    if (i + position) % 2 == 0 and r_send is not None:
      # send your value to your right neighbor
      process_lock.acquire()
      r_send[1].send(a_      )
      process_lock.release()

      # receive your right neighbor's value
      process_lock.acquire()
      __a								=       rr_cv[0].recv()
      process_lock.release()

      # take the lower value since you are on the left
      __a								=       min(a_					,       a_      )
    elif (i + position) % 2 != 0 and l_send is not None:
      # send your value to your left neighbor
      process_lock.acquire()
      l_send[1].send(a_      )
      process_lock.release()

      # receive your left neighbor's value
      process_lock.acquire()
      __a								=       lr_cv[0].recv()
      process_lock.release()

      # take the higher value since you are on the right
      __a								=       max(a_					,       a_      )
    # after all swaps are performed, send the values back to main
  result_pipe[1].send(a_      )


def     SCREAMING_SNAKE_CASE							(   a_						:				List[str]      ):
  __a								=       []
  __a								=       []
  # initialize the list of pipes where the values will be retrieved
  for _ in arr:
    result_pipe.append(Pipe()      )
  # creates the processes
  # the first and last process only have one neighbor so they are made outside
  # of the loop
  __a								=       Pipe()
  __a								=       Pipe()
  process_array_.append(
      Process(
          target=a_					,       args=(0, arr[0], None, temp_rs, None, temp_rr, result_pipe[0])					,       )      )
  __a								=       temp_rs
  __a								=       temp_rr

  for i in range(1					,       len(a_      ) - 1      ):
    __a								=       Pipe()
    __a								=       Pipe()
    process_array_.append(
        Process(
            target=a_					,       args=(i, arr[i], temp_ls, temp_rs, temp_lr, temp_rr, result_pipe[i])					,       )      )
    __a								=       temp_rs
    __a								=       temp_rr

  process_array_.append(
      Process(
          target=a_					,       args=(
              len(a_      ) - 1,
              arr[len(a_      ) - 1],
              temp_ls,
              None,
              temp_lr,
              None,
              result_pipe[len(a_      ) - 1],
          )					,       )      )

  # start the processes
  for p in process_array_:
    p.start()

  # wait for the processes to end and write their values to the list
  for p in range(0					,       len(a_      )      ):
    __a								=       result_pipe[p][0].recv()
    process_array_[p].join()
  return arr


def     SCREAMING_SNAKE_CASE							(   ):
  __a								=       list(range(10					,       0					,       -1      )      )
  print('Initial List'      )
  print(*a_      )
  __a								=       odd_even_transposition(a_      )
  print('Sorted List\n'      )
  print(*a_      )


if __name__ == "__main__":
  main()



