depth first search args g dictionary of edges s starting node vars vis set of visited nodes s traversal stack breadth first search args g dictionary of edges s starting node vars vis set of visited nodes q traversal stack 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 topological sort reading an adjacency matrix n intinput strip a for in rangen a appendtuplemapint input strip split return a n def floyaandn a n aandn dist lista path 0 n for i in rangen for k in rangen for i in rangen for j in rangen if distij distik distkj distij distik distkj pathik k printdist def primg s dist known path s 0 set s 0 while true if lenknown leng 1 break mini 100000 for i in dist if i not in known and disti mini mini disti u i known addu for v in gu if v0 not in known and v1 dist getv0 100000 distv0 v1 pathv0 u return dist def edglist r get the edges and number of edges from the user parameters none returns tuple a tuple containing a list of edges and number of edges example simulate user input for 3 edges and 4 vertices 1 2 2 3 3 4 inputdata 4 3n1 2n2 3n3 4n import sys io originalinput sys stdin sys stdin io stringioinputdata redirect stdin for testing edglist 1 2 2 3 3 4 4 sys stdin originalinput restore original stdin kruskal s mst algorithm args e edge list n number of nodes vars s set of all nodes as unique disjoint sets initially sort edges on the basis of distance find the isolated node in the graph parameters graph dict a dictionary representing a graph returns list a list of isolated nodes examples graph1 1 2 3 2 1 3 3 1 2 4 findisolatednodesgraph1 4 graph2 a b c b a c a d findisolatednodesgraph2 d graph3 x y z findisolatednodesgraph3 x y z graph4 1 2 3 2 1 3 3 1 2 findisolatednodesgraph4 graph5 findisolatednodesgraph5 depth first search args g dictionary of edges s starting node vars vis set of visited nodes s traversal stack breadth first search args g dictionary of edges s starting node vars vis set of visited nodes q traversal stack 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 topological sort since oth index is ignored reading an adjacency matrix reading an adjacency matrix parameters none returns tuple a tuple containing a list of edges and number of edges example simulate user input for 3 nodes input_data 4 n0 1 0 1 n1 0 1 0 n0 1 0 1 n1 0 1 0 n import sys io original_input sys stdin sys stdin io stringio input_data redirect stdin for testing adjm 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 4 sys stdin original_input restore original stdin 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 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 accepting edge list vars n number of nodes m number of edges returns l edge list n number of nodes get the edges and number of edges from the user parameters none returns tuple a tuple containing a list of edges and number of edges example simulate user input for 3 edges and 4 vertices 1 2 2 3 3 4 input_data 4 3 n1 2 n2 3 n3 4 n import sys io original_input sys stdin sys stdin io stringio input_data redirect stdin for testing edglist 1 2 2 3 3 4 4 sys stdin original_input restore original stdin kruskal s mst algorithm args e edge list n number of nodes vars s set of all nodes as unique disjoint sets initially sort edges on the basis of distance find the isolated node in the graph parameters graph dict a dictionary representing a graph returns list a list of isolated nodes examples graph1 1 2 3 2 1 3 3 1 2 4 find_isolated_nodes graph1 4 graph2 a b c b a c a d find_isolated_nodes graph2 d graph3 x y z find_isolated_nodes graph3 x y z graph4 1 2 3 2 1 3 3 1 2 find_isolated_nodes graph4 graph5 find_isolated_nodes graph5
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)





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()





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)





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 and 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])





def topo(g, ind=None, q=None):
    if q is None:
        q = [1]
    if ind is None:
        ind = [0] * (len(g) + 1)  
        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)





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





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)





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 and v[1] < dist.get(v[0], 100000):
                dist[v[0]] = v[1]
                path[v[0]] = u
    return dist





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





def krusk(e_and_n):
    
    (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


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