from collections import deque

def find_pasha_operations(n, m, original_edges, modified_edges):
    def build_graph(edges):
        graph = {i: set() for i in range(1, n+1)}
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)
        return graph
    
    def bfs(graph, start, target):
        queue = deque([(start, [])])
        visited = set([start])
        
        while queue:
            node, path = queue.popleft()
            if node == target:
                return path
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append((neighbor, path + [(node, neighbor)]))
                    visited.add(neighbor)
        
        return None
    
    original_graph = build_graph(original_edges)
    modified_graph = build_graph(modified_edges)
    complete_graph = build_graph([(i, j) for i in range(1, n+1) for j in range(i+1, n+1)])
    
    for u, v in original_edges:
        if u not in modified_graph[v] and v not in modified_graph[u]:
            if u not in complete_graph[v]:
                for c in range(1, n+1):
                    if c != u and c != v and c not in original_graph[u] and c not in original_graph[v]:
                        complete_graph[u].add(c)
                        complete_graph[v].add(c)
                        complete_graph[c].add(u)
                        complete_graph[c].add(v)
                        modified_graph[u].add(v)
                        modified_graph[v].add(u)
                        return "YES", [(u, v, c)]
            else:
                modified_graph[u].add(v)
                modified_graph[v].add(u)
    
    for u, v in modified_edges:
        if u not in original_graph[v] and v not in original_graph[u]:
            return "NO"
        
    start_node = modified_edges[0][0]
    target_node = modified_edges[-1][1]
    operations = bfs(modified_graph, start_node, target_node)
    
    if operations:
        return "YES", operations
    else:
        return "NO"

# Пример использования
n = 5
m = 4
original_edges = [(1, 2), (2, 3), (3, 4), (4, 5)]
modified_edges = [(1, 2), (2, 4), (3, 4), (4, 5)]

result, operations = find_pasha_operations(n, m, original_edges, modified_edges)
print(result)
if result == "YES":
    print(operations)
