




from collections import deque



def    UpperCAmelCase							(  _snake_case				):
							return input(_snake_case				).strip().split(''' '''				)



def    UpperCAmelCase							(  _snake_case    ,			_snake_case				):
							lowerCAmelCase =		{}
							for i in range(_snake_case				):
														lowerCAmelCase =		[]

							for e in range(_snake_case				):
														lowerCAmelCase ,  lowerCAmelCase =		(int(_snake_case				) for i in _input(F"""Edge {e + 1}: <node1> <node2> """				))
														graph[x].append(_snake_case				)
							return graph



def    UpperCAmelCase							(  _snake_case    ,			_snake_case				):
							lowerCAmelCase =		{}
							for i in range(_snake_case				):
														lowerCAmelCase =		[]

							for e in range(_snake_case				):
														lowerCAmelCase ,  lowerCAmelCase =		(int(_snake_case				) for i in _input(F"""Edge {e + 1}: <node1> <node2> """				))
														graph[x].append(_snake_case				)
														graph[y].append(_snake_case				)
							return graph



def    UpperCAmelCase							(  _snake_case    ,			_snake_case				):
							lowerCAmelCase =		{}
							for i in range(_snake_case				):
														lowerCAmelCase =		[]

							for e in range(_snake_case				):
														lowerCAmelCase ,  lowerCAmelCase ,  lowerCAmelCase =		(int(_snake_case				) for i in _input(F"""Edge {e + 1}: <node1> <node2> <weight> """				))
														graph[x].append((y, w)				)
														graph[y].append((x, w)				)
							return graph


if __name__ == "__main__":
		UpperCAmelCase_,UpperCAmelCase_    =(int(i) for i in _input("""Number of nodes and edges: """))

		UpperCAmelCase_    =int(
		    _input(
		        """Press 1 or 2 or 3 \n"""
		        """1. Unweighted directed \n"""
		        """2. Unweighted undirected \n"""
		        """3. Weighted undirected \n"""
		    )[0]
		)

		UpperCAmelCase_    ={
		    1: initialize_unweighted_directed_graph,
		    2: initialize_unweighted_undirected_graph,
		    3: initialize_weighted_undirected_graph,
		}[graph_choice](n, m)



def    UpperCAmelCase							(  _snake_case    ,			_snake_case				):
							lowerCAmelCase ,  lowerCAmelCase =		{s}, [s]
							print(_snake_case				)
							while _s:
														lowerCAmelCase =		0
														for i in g[_s[-1]]:
																					if i not in vis:
																												_s.append(_snake_case				)
																												vis.add(_snake_case				)
																												lowerCAmelCase =		1
																												print(_snake_case				)
																												break
														if not flag:
																					_s.pop()



def    UpperCAmelCase							(  _snake_case    ,			_snake_case				):
							lowerCAmelCase ,  lowerCAmelCase =		{s}, deque([s]				)
							print(_snake_case				)
							while q:
														lowerCAmelCase =		q.popleft()
														for v in g[u]:
																					if v not in vis:
																												vis.add(_snake_case				)
																												q.append(_snake_case				)
																												print(_snake_case				)



def    UpperCAmelCase							(  _snake_case    ,			_snake_case				):
							lowerCAmelCase ,  lowerCAmelCase ,  lowerCAmelCase =		{s: 0}, set(), {s: 0}
							while True:
														if len(_snake_case				) == len(_snake_case				) - 1:
																					break
														lowerCAmelCase =		100000
														for i in dist:
																					if i not in known and dist[i] < mini:
																												lowerCAmelCase =		dist[i]
																												lowerCAmelCase =		i
														known.add(_snake_case				)
														for v in g[u]:
																					if v[0] not in known and dist[u] + v[1] < dist.get(v[0]    ,			100000				):
																												lowerCAmelCase =		dist[u] + v[1]
																												lowerCAmelCase =		u
							for i in dist:
														if i != s:
																					print(dist[i]				)



def    UpperCAmelCase							(  _snake_case    ,			_snake_case=None    ,			_snake_case=None				):
							if q is None:
														lowerCAmelCase =		[1]
							if ind is None:
														lowerCAmelCase =		[0] * (len(_snake_case				) + 1)  # SInce oth Index is ignored
														for u in g:
																					for v in g[u]:
																												ind[v] += 1
														lowerCAmelCase =		deque()
														for i in g:
																					if ind[i] == 0:
																												q.append(_snake_case				)
							if len(_snake_case				) == 0:
														return
							lowerCAmelCase =		q.popleft()
							print(_snake_case				)
							for w in g[v]:
														ind[w] -= 1
														if ind[w] == 0:
																					q.append(_snake_case				)
							topo(_snake_case    ,			_snake_case    ,			_snake_case				)



def    UpperCAmelCase							(  ):
							lowerCAmelCase =		input().strip()
							lowerCAmelCase =		[]
							for _ in range(_snake_case				):
														a.append(map(_snake_case    ,			input().strip().split()				)				)
							return a, n



def    UpperCAmelCase							(  _snake_case				):
							((lowerCAmelCase) ,  (lowerCAmelCase)) =		a_and_n
							lowerCAmelCase =		list(_snake_case				)
							lowerCAmelCase =		[[0] * n for i in range(_snake_case				)]
							for k in range(_snake_case				):
														for i in range(_snake_case				):
																					for j in range(_snake_case				):
																												if dist[i][j] > dist[i][k] + dist[k][j]:
																																			lowerCAmelCase =		dist[i][k] + dist[k][j]
																																			lowerCAmelCase =		k
							print(_snake_case				)



def    UpperCAmelCase							(  _snake_case    ,			_snake_case				):
							lowerCAmelCase ,  lowerCAmelCase ,  lowerCAmelCase =		{s: 0}, set(), {s: 0}
							while True:
														if len(_snake_case				) == len(_snake_case				) - 1:
																					break
														lowerCAmelCase =		100000
														for i in dist:
																					if i not in known and dist[i] < mini:
																												lowerCAmelCase =		dist[i]
																												lowerCAmelCase =		i
														known.add(_snake_case				)
														for v in g[u]:
																					if v[0] not in known and v[1] < dist.get(v[0]    ,			100000				):
																												lowerCAmelCase =		v[1]
																												lowerCAmelCase =		u
							return dist



def    UpperCAmelCase							(  ):
							lowerCAmelCase ,  lowerCAmelCase =		map(_snake_case    ,			input().split(''' '''				)				)
							lowerCAmelCase =		[]
							for _ in range(_snake_case				):
														edges.append(map(_snake_case    ,			input().split(''' '''				)				)				)
							return edges, n



def    UpperCAmelCase							(  _snake_case				):
							# Sort edges on the basis of distance
							((lowerCAmelCase) ,  (lowerCAmelCase)) =		e_and_n
							e.sort(reverse=_snake_case    ,			key=lambda _snake_case				: x[2]				)
							lowerCAmelCase =		[{i} for i in range(1    ,			n + 1				)]
							while True:
														if len(_snake_case				) == 1:
																					break
														print(_snake_case				)
														lowerCAmelCase =		e.pop()
														for i in range(len(_snake_case				)				):
																					if x[0] in s[i]:
																												break
														for j in range(len(_snake_case				)				):
																					if x[1] in s[j]:
																												if i == j:
																																			break
																												s[j].update(s[i]				)
																												s.pop(_snake_case				)
																												break



def    UpperCAmelCase							(  _snake_case				):
							lowerCAmelCase =		[]
							for node in graph:
														if not graph[node]:
																					isolated.append(_snake_case				)
							return isolated









from itertools import permutations



def    UpperCAmelCase							(  _snake_case = 5				):
							if gon_side < 3 or gon_side > 5:
														raise ValueError('''gon_side must be in the range [3, 5]'''				)

							# Since it's 16, we know 10 is on the outer ring
							# Put the big numbers at the end so that they are never the first number
							lowerCAmelCase =		list(range(gon_side + 1    ,			0    ,			-1				)				)
							lowerCAmelCase =		list(range(gon_side + 2    ,			gon_side * 2 + 1				)				)

							for perm in permutations(small_numbers + big_numbers				):
														lowerCAmelCase =		generate_gon_ring(_snake_case    ,			list(_snake_case				)				)
														if is_magic_gon(_snake_case				):
																					return int(''''''.join(str(_snake_case				) for n in numbers				)				)

							lowerCAmelCase =		F"""Magic {gon_side}-gon ring is impossible"""
							raise ValueError(_snake_case				)



def    UpperCAmelCase							(  _snake_case    ,			_snake_case				):
							lowerCAmelCase =		[0] * (gon_side * 3)
							lowerCAmelCase =		perm[0:3]
							perm.append(perm[1]				)

							lowerCAmelCase =		1 if gon_side < 5 else 2

							for i in range(1    ,			len(_snake_case				) // 3 + magic_number				):
														lowerCAmelCase =		perm[2 * i + 1]
														lowerCAmelCase =		result[3 * i - 1]
														lowerCAmelCase =		perm[2 * i + 2]

							return result



def    UpperCAmelCase							(  _snake_case				):
							if len(_snake_case				) % 3 != 0:
														raise ValueError('''a gon ring should have a length that is a multiple of 3'''				)

							if min(numbers[::3]				) != numbers[0]:
														return False

							lowerCAmelCase =		sum(numbers[:3]				)

							return all(sum(numbers[i : i + 3]				) == total for i in range(3    ,			len(_snake_case				)    ,			3				)				)


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



