from collections import deque


def _input(message):
 return input(message).strip().split(" ")


def initialize_unweighted_directed_graph(
 node_count: int, edge_count: int
) -> dict[int, list[int]]:
 graph: dict[int, list[int]] = {}
 for i in range(node_count):
 graph[i + 1] = []

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


def initialize_unweighted_undirected_graph(
 node_count: int, edge_count: int
) -> dict[int, list[int]]:
 graph: dict[int, list[int]] = {}
 for i in range(node_count):
 graph[i + 1] = []

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


def initialize_weighted_undirected_graph(
 node_count: int, edge_count: int
) -> dict[int, list[tuple[int, int]]]:
 graph: dict[int, list[tuple[int, int]]] = {}
 for i in range(node_count):
 graph[i + 1] = []

 for e in range(edge_count):
 x, y, w = (int(i) 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__":
 n, m = (int(i) for i in _input("Number of nodes and edges: "))

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

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


"""
--------------------------------------------------------------------------------
 Depth First Search.
 Args : G - Dictionary of edges
 s - Starting Node
 Vars : vis - Set of visited nodes
 S - Traversal Stack
--------------------------------------------------------------------------------
"""


def dfs(G, s):
 vis, S = {s}, [s]
 print(s)
 while S:
 flag = 0
 for i in G[S[-1]]:
 if i not in vis:
 S.append(i)
 vis.add(i)
 flag = 1
 print(i)
 break
 if not flag:
 S.pop()


"""
--------------------------------------------------------------------------------
 Breadth First Search.
 Args : G - Dictionary of edges
 s - Starting Node
 Vars : vis - Set of visited nodes
 Q - Traversal Stack
--------------------------------------------------------------------------------
"""


def bfs(G, s):
 vis, Q = {s}, deque([s])
 print(s)
 while Q:
 u = Q.popleft()
 for v in G[u]:
 if v not in vis:
 vis.add(v)
 Q.append(v)
 print(v)


"""
--------------------------------------------------------------------------------
 Dijkstra's shortest path Algorithm
 Args : G - Dictionary of edges
 s - Starting Node
 Vars : dist - Dictionary storing shortest distance from s to every other node
 known - Set of knows nodes
 path - Preceding node in path
--------------------------------------------------------------------------------
"""


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


"""
--------------------------------------------------------------------------------
 Topological Sort
--------------------------------------------------------------------------------
"""


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


"""
--------------------------------------------------------------------------------
 Reading an Adjacency matrix
--------------------------------------------------------------------------------
"""


def adjm():
 n = input().strip()
 a = []
 for i in range(n):
 a.append(map(int, input().strip().split()))
 return a, n


"""
--------------------------------------------------------------------------------
 Floyd Warshall's algorithm
 Args : G - Dictionary of edges
 s - Starting Node
 Vars : dist - Dictionary storing shortest distance from s to every other node
 known - Set of knows nodes
 path - Preceding node in path

--------------------------------------------------------------------------------
"""


def floy(A_and_n):
 (A, n) = A_and_n
 dist = list(A)
 path = [[0] * n for i in range(n)]
 for k in range(n):
 for i in range(n):
 for j in range(n):
 if dist[i][j] > dist[i][k] + dist[k][j]:
 dist[i][j] = dist[i][k] + dist[k][j]
 path[i][k] = k
 print(dist)


"""
--------------------------------------------------------------------------------
 Prim's MST Algorithm
 Args : G - Dictionary of edges
 s - Starting Node
 Vars : dist - Dictionary storing shortest distance from s to nearest node
 known - Set of knows nodes
 path - Preceding node in path
--------------------------------------------------------------------------------
"""


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


"""
--------------------------------------------------------------------------------
 Accepting Edge list
 Vars : n - Number of nodes
 m - Number of edges
 Returns : l - Edge list
 n - Number of Nodes
--------------------------------------------------------------------------------
"""


def edglist():
 n, m = map(int, input().split(" "))
 edges = []
 for i in range(m):
 edges.append(map(int, input().split(" ")))
 return edges, n


"""
--------------------------------------------------------------------------------
 Kruskal's MST Algorithm
 Args : E - Edge list
 n - Number of Nodes
 Vars : s - Set of all nodes as unique disjoint sets (initially)
--------------------------------------------------------------------------------
"""


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


# find the isolated node in the graph
def find_isolated_nodes(graph):
 isolated = []
 for node in graph:
 if not graph[node]:
 isolated.append(node)
 return isolated