



"""simple docstring"""







from collections import deque

def 	lowerCAmelCase__      (  lowerCamelCase__      )			->				Tuple:
							return input(lowerCamelCase__      ).strip().split(' '      )

def 	lowerCAmelCase__      (  lowerCamelCase__					,   lowerCamelCase__      )			->				dict[int, list[int]]:
							A    =       {}
							for i in range(lowerCamelCase__      ):
														A    =       []

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

def 	lowerCAmelCase__      (  lowerCamelCase__					,   lowerCamelCase__      )			->				dict[int, list[int]]:
							A    =       {}
							for i in range(lowerCamelCase__      ):
														A    =       []

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

def 	lowerCAmelCase__      (  lowerCamelCase__					,   lowerCamelCase__      )			->				dict[int, list[tuple[int, int]]]:
							A    =       {}
							for i in range(lowerCamelCase__      ):
														A    =       []

							for e in range(lowerCamelCase__      ):
														A   ,	A   ,	A    =       (int(lowerCamelCase__      ) 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__":
							A     ,					A     =      (int(i) for i in _input('Number of nodes and edges: '))

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

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

def 	lowerCAmelCase__      (  lowerCamelCase__					,   lowerCamelCase__      )			->				List[Any]:
							A   ,	A    =       {s}, [s]
							print(lowerCamelCase__      )
							while _s:
														A    =       0
														for i in g[_s[-1]]:
																					if i not in vis:
																												_s.append(lowerCamelCase__      )
																												vis.add(lowerCamelCase__      )
																												A    =       1
																												print(lowerCamelCase__      )
																												break
														if not flag:
																					_s.pop()

def 	lowerCAmelCase__      (  lowerCamelCase__					,   lowerCamelCase__      )			->				List[Any]:
							A   ,	A    =       {s}, deque([s]      )
							print(lowerCamelCase__      )
							while q:
														A    =       q.popleft()
														for v in g[u]:
																					if v not in vis:
																												vis.add(lowerCamelCase__      )
																												q.append(lowerCamelCase__      )
																												print(lowerCamelCase__      )

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

def 	lowerCAmelCase__      (  lowerCamelCase__					,   lowerCamelCase__=None					,   lowerCamelCase__=None      )			->				Union[str, Any]:
							if q is None:
														A    =       [1]
							if ind is None:
														A    =       [0] * (len(lowerCamelCase__      ) + 1)  # SInce oth Index is ignored
														for u in g:
																					for v in g[u]:
																												ind[v] += 1
														A    =       deque()
														for i in g:
																					if ind[i] == 0:
																												q.append(lowerCamelCase__      )
							if len(lowerCamelCase__      ) == 0:
														return
							A    =       q.popleft()
							print(lowerCamelCase__      )
							for w in g[v]:
														ind[w] -= 1
														if ind[w] == 0:
																					q.append(lowerCamelCase__      )
							topo(lowerCamelCase__					,   lowerCamelCase__					,   lowerCamelCase__      )

def 	lowerCAmelCase__      (  )			->				Optional[int]:
							A    =       input().strip()
							A    =       []
							for _ in range(lowerCamelCase__      ):
														a.append(map(lowerCamelCase__					,   input().strip().split()      )      )
							return a, n

def 	lowerCAmelCase__      (  lowerCamelCase__      )			->				Union[str, Any]:
							((A)   ,	(A))    =       a_and_n
							A    =       list(lowerCamelCase__      )
							A    =       [[0] * n for i in range(lowerCamelCase__      )]
							for k in range(lowerCamelCase__      ):
														for i in range(lowerCamelCase__      ):
																					for j in range(lowerCamelCase__      ):
																												if dist[i][j] > dist[i][k] + dist[k][j]:
																																			A    =       dist[i][k] + dist[k][j]
																																			A    =       k
							print(lowerCamelCase__      )

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

def 	lowerCAmelCase__      (  )			->				Optional[int]:
							A   ,	A    =       map(lowerCamelCase__					,   input().split(' '      )      )
							A    =       []
							for _ in range(lowerCamelCase__      ):
														edges.append(map(lowerCamelCase__					,   input().split(' '      )      )      )
							return edges, n

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

def 	lowerCAmelCase__      (  lowerCamelCase__      )			->				Union[str, Any]:
							A    =       []
							for node in graph:
														if not graph[node]:
																					isolated.append(lowerCamelCase__      )
							return isolated








"""simple docstring"""







from collections import namedtuple

A     =      namedtuple('from_to', 'from_ to')

A     =      {
    'millimeter': 'mm',
    'centimeter': 'cm',
    'meter': 'm',
    'kilometer': 'km',
    'inch': 'in',
    'inche': 'in',  # Trailing 's' has been stripped off
    'feet': 'ft',
    'foot': 'ft',
    'yard': 'yd',
    'mile': 'mi',
}

A     =      {
    'mm': from_to(0.001, 1_0_0_0),
    'cm': from_to(0.01, 1_0_0),
    'm': from_to(1, 1),
    'km': from_to(1_0_0_0, 0.001),
    'in': from_to(0.0254, 39.3701),
    'ft': from_to(0.3048, 3.2_8084),
    'yd': from_to(0.9144, 1.0_9361),
    'mi': from_to(1609.34, 0.0_0062_1371),
}

def 	lowerCAmelCase__      (  lowerCamelCase__					,   lowerCamelCase__					,   lowerCamelCase__      )			->				float:
							A    =       from_type.lower().rstrip('s'      )
							A    =       TYPE_CONVERSION.get(lowerCamelCase__					,   lowerCamelCase__      )
							A    =       to_type.lower().rstrip('s'      )
							A    =       TYPE_CONVERSION.get(lowerCamelCase__					,   lowerCamelCase__      )
							if new_from not in METRIC_CONVERSION:
														A    =       (
														    f"""Invalid 'from_type' value: {from_type!r}.\n"""
														    f"""Conversion abbreviations are: {', '.join(lowerCamelCase__      )}"""
														)
														raise ValueError(lowerCamelCase__      )
							if new_to not in METRIC_CONVERSION:
														A    =       (
														    f"""Invalid 'to_type' value: {to_type!r}.\n"""
														    f"""Conversion abbreviations are: {', '.join(lowerCamelCase__      )}"""
														)
														raise ValueError(lowerCamelCase__      )
							return value * METRIC_CONVERSION[new_from].from_ * METRIC_CONVERSION[new_to].to


if __name__ == "__main__":
							import doctest

							doctest.testmod()



