



'''simple docstring'''



import heapq as hq
import math
from collections.abc import Iterator





class _UpperCamelCase		:





				'''simple docstring'''





				def __init__(							self  :  List[Any]  ,       _lowerCAmelCase  :  Union[str, Any]):







											'''simple docstring'''

											__lowercase       	=str(id_)
											__lowercase       	=None
											__lowercase       	=None
											__lowercase       	=[]
											__lowercase       	={}  # {vertex:distance}

				def __lt__(							self  :  Optional[Any]  ,       _lowerCAmelCase  :  Dict):







											'''simple docstring'''

											return self.key < other.key

				def __repr__(							self  :  Optional[int]):







											'''simple docstring'''

											return self.id

				def 				__lowerCamelCase     (							self  :  int  ,       _lowerCAmelCase  :  Optional[Any]):







											'''simple docstring'''

											self.neighbors.append(_lowerCAmelCase)

				def 				__lowerCamelCase     (							self  :  Union[str, Any]  ,       _lowerCAmelCase  :  List[str]  ,       _lowerCAmelCase  :  Optional[int]):







											'''simple docstring'''

											__lowercase       	=weight



def   _A       (   _lowerCAmelCase  ,   _lowerCAmelCase  ,   _lowerCAmelCase  ,   _lowerCAmelCase					):



							"""simple docstring"""



							graph[a - 1].add_neighbor(graph[b - 1]					)
							graph[b - 1].add_neighbor(graph[a - 1]					)
							# add the edges:
							graph[a - 1].add_edge(graph[b - 1]  ,   _lowerCAmelCase					)
							graph[b - 1].add_edge(graph[a - 1]  ,   _lowerCAmelCase					)



def   _A       (   _lowerCAmelCase  ,   _lowerCAmelCase					):



							"""simple docstring"""



							__lowercase       	=[]
							for u in graph:
														__lowercase       	=math.inf
														__lowercase       	=None
							__lowercase       	=0
							__lowercase       	=graph[:]
							while q:
														__lowercase       	=min(_lowerCAmelCase					)
														q.remove(_lowerCAmelCase					)
														for v in u.neighbors:
																					if (v in q) and (u.edges[v.id] < v.key):
																												__lowercase       	=u
																												__lowercase       	=u.edges[v.id]
							for i in range(1  ,   len(_lowerCAmelCase					)					):
														a.append((int(graph[i].id					) + 1, int(graph[i].pi.id					) + 1)					)
							return a



def   _A       (   _lowerCAmelCase  ,   _lowerCAmelCase					):



							"""simple docstring"""



							for u in graph:
														__lowercase       	=math.inf
														__lowercase       	=None
							__lowercase       	=0

							__lowercase       	=list(_lowerCAmelCase					)
							hq.heapify(_lowerCAmelCase					)

							while h:
														__lowercase       	=hq.heappop(_lowerCAmelCase					)
														for v in u.neighbors:
																					if (v in h) and (u.edges[v.id] < v.key):
																												__lowercase       	=u
																												__lowercase       	=u.edges[v.id]
																												hq.heapify(_lowerCAmelCase					)

							for i in range(1  ,   len(_lowerCAmelCase					)					):
														yield (int(graph[i].id					) + 1, int(graph[i].pi.id					) + 1)



def   _A       (   ):



							"""simple docstring"""





if __name__ == "__main__":
		import doctest

		doctest.testmod()








'''simple docstring'''



from functools import lru_cache



def   _A       (   _lowerCAmelCase					):



							"""simple docstring"""



							__lowercase       	=2
							__lowercase       	=set()
							while i * i <= n:
														if n % i:
																					i += 1
														else:
																					n //= i
																					factors.add(_lowerCAmelCase					)
							if n > 1:
														factors.add(_lowerCAmelCase					)
							return factors



@lru_cache
def   _A       (   _lowerCAmelCase					):



							"""simple docstring"""



							return len(unique_prime_factors(_lowerCAmelCase					)					)



def   _A       (   _lowerCAmelCase					):



							"""simple docstring"""



							return len(set(_lowerCAmelCase					)					) in (0, 1)



def   _A       (   _lowerCAmelCase					):



							"""simple docstring"""



							__lowercase       	=2

							while True:
														# Increment each value of a generated range
														__lowercase       	=[base + i for i in range(_lowerCAmelCase					)]

														# Run elements through out unique_prime_factors function
														# Append our target number to the end.
														__lowercase       	=[upf_len(_lowerCAmelCase					) for x in group]
														checker.append(_lowerCAmelCase					)

														# If all numbers in the list are equal, return the group variable.
														if equality(_lowerCAmelCase					):
																					return group

														# Increment our base variable by 1
														base += 1



def   _A       (   _lowerCAmelCase = 4					):



							"""simple docstring"""



							__lowercase       	=run(_lowerCAmelCase					)
							return results[0] if len(_lowerCAmelCase					) else None


if __name__ == "__main__":
		print(solution())



