
'''simple docstring'''







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


class 						__UpperCAmelCase      :


							def __init__(       self  ):





								"""simple docstring"""






								_snake_case   						=		{}


							def  lowerCamelCase				(       self    ,   lowerCAmelCase_    ,   lowerCAmelCase_    ,   lowerCAmelCase_=1  ):





								"""simple docstring"""






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


							def  lowerCamelCase				(       self  ):





								"""simple docstring"""






								return list(self.graph  )


							def  lowerCamelCase				(       self    ,   lowerCAmelCase_    ,   lowerCAmelCase_  ):





								"""simple docstring"""






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


							def  lowerCamelCase				(       self    ,   lowerCAmelCase_=-2    ,   lowerCAmelCase_=-1  ):





								"""simple docstring"""






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

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

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

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


							def  lowerCamelCase				(       self    ,   lowerCAmelCase_=-1  ):





								"""simple docstring"""






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


							def  lowerCamelCase				(       self    ,   lowerCAmelCase_=-2  ):





								"""simple docstring"""






								_snake_case   						=		deque()
								_snake_case   						=		[]
								if s == -2:
									_snake_case   						=		list(self.graph  )[0]
								d.append(SCREAMING_SNAKE_CASE__  )
								visited.append(SCREAMING_SNAKE_CASE__  )
								while d:
									_snake_case   						=		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    ,   lowerCAmelCase_  ):





								"""simple docstring"""






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


							def  lowerCamelCase				(       self    ,   lowerCAmelCase_  ):





								"""simple docstring"""






								return len(self.graph[u]  )


							def  lowerCamelCase				(       self    ,   lowerCAmelCase_=-2  ):





								"""simple docstring"""






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

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

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

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


							def  lowerCamelCase				(       self  ):





								"""simple docstring"""






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

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

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

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


							def  lowerCamelCase				(       self  ):





								"""simple docstring"""






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

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

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

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


							def  lowerCamelCase				(       self    ,   lowerCAmelCase_=-2    ,   lowerCAmelCase_=-1  ):





								"""simple docstring"""






								_snake_case   						=		time()
								self.dfs(SCREAMING_SNAKE_CASE__    ,   SCREAMING_SNAKE_CASE__  )
								_snake_case   						=		time()
								return end - begin




							def  lowerCamelCase				(       self    ,   lowerCAmelCase_=-2  ):





								"""simple docstring"""






								_snake_case   						=		time()
								self.bfs(SCREAMING_SNAKE_CASE__  )
								_snake_case   						=		time()
								return end - begin


class 						__UpperCAmelCase      :


							def __init__(       self  ):





								"""simple docstring"""






								_snake_case   						=		{}


							def  lowerCamelCase				(       self    ,   lowerCAmelCase_    ,   lowerCAmelCase_    ,   lowerCAmelCase_=1  ):





								"""simple docstring"""






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


							def  lowerCamelCase				(       self    ,   lowerCAmelCase_    ,   lowerCAmelCase_  ):





								"""simple docstring"""






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


							def  lowerCamelCase				(       self    ,   lowerCAmelCase_=-2    ,   lowerCAmelCase_=-1  ):





								"""simple docstring"""






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

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

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

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


							def  lowerCamelCase				(       self    ,   lowerCAmelCase_=-1  ):





								"""simple docstring"""






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


							def  lowerCamelCase				(       self    ,   lowerCAmelCase_=-2  ):





								"""simple docstring"""






								_snake_case   						=		deque()
								_snake_case   						=		[]
								if s == -2:
									_snake_case   						=		list(self.graph  )[0]
								d.append(SCREAMING_SNAKE_CASE__  )
								visited.append(SCREAMING_SNAKE_CASE__  )
								while d:
									_snake_case   						=		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    ,   lowerCAmelCase_  ):





								"""simple docstring"""






								return len(self.graph[u]  )


							def  lowerCamelCase				(       self  ):





								"""simple docstring"""






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

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

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

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


							def  lowerCamelCase				(       self  ):





								"""simple docstring"""






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

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

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

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


							def  lowerCamelCase				(       self  ):





								"""simple docstring"""






								return list(self.graph  )


							def  lowerCamelCase				(       self    ,   lowerCAmelCase_=-2    ,   lowerCAmelCase_=-1  ):





								"""simple docstring"""






								_snake_case   						=		time()
								self.dfs(SCREAMING_SNAKE_CASE__    ,   SCREAMING_SNAKE_CASE__  )
								_snake_case   						=		time()
								return end - begin




							def  lowerCamelCase				(       self    ,   lowerCAmelCase_=-2  ):





								"""simple docstring"""






								_snake_case   						=		time()
								self.bfs(SCREAMING_SNAKE_CASE__  )
								_snake_case   						=		time()
								return end - begin








"""simple docstring"""
from typing import Any



def      __lowerCamelCase   (							a_     :		list							)			->      list[Any]:
      if not input_list:
            return []
      __SCREAMING_SNAKE_CASE   :int						=  [input_list.count(a_							) for value in input_list]
      __SCREAMING_SNAKE_CASE   :str						=  max(a_							)  # Gets the maximum count in the input list.
      # Gets values of modes
      return sorted({input_list[i] for i, value in enumerate(a_							) if value == y}							)


if __name__ == "__main__":
  import doctest

  doctest.testmod()