def dfs(graph, node, visited):
    visited[node] = True
    
    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs(graph, neighbor, visited)
    
    return visited

def find_operations(initial_graph, current_graph):
    p = len(initial_graph)
    
    # Создаем список смежности для графа
    initial_adj_list = [[] for _ in range(p+1)]
    current_adj_list = [[] for _ in range(p+1)]
    
    for u in range(1, p+1):
        for v in range(u+1, p+1):
            if (u, v) in initial_graph:
                initial_adj_list[u].append(v)
                initial_adj_list[v].append(u)
                
            if (u, v) in current_graph:
                current_adj_list[u].append(v)
                current_adj_list[v].append(u)
    
    # Используем DFS для проверки, является ли текущий граф
    # достижимым из исходного графа
    visited = [False] * (p+1)
    initial_reachable = dfs(initial_adj_list, 1, visited)
    
    visited = [False] * (p+1)
    current_reachable = dfs(current_adj_list, 1, visited)
    
    # Проверяем, что все вершины текущего графа достижимы из исходного
    if not all(initial_reachable[i] == current_reachable[i] for i in range(1, p+1)):
        return "Последовательность действий не найдена."
    
    # Находим ребра, которые отсутствуют в текущем графе
    missing_edges = []
    
    for u in range(1, p+1):
        for v in range(u+1, p+1):
            if (u, v) not in current_graph and initial_graph != current_graph:
                missing_edges.append((u, v))
    
    return missing_edges


Пример использования этой функции:

# Исходный граф и текущий граф
initial_graph = [(1, 2), (1, 3), (2, 3), (3, 4)]
current_graph = [(1, 3), (2, 3), (3, 4), (4, 5)]

result = find_operations(initial_graph, current_graph)
print(result)
