1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
from collections import deque

def parse_input(input_str):
    lines = input_str.strip().split("\n")
    graph1 = set()
    graph2 = set()
    n, m1 = map(int, lines[:2])
    for line in lines[2:2 + m1]:
        a, b = map(int, line.split())
        graph1.add((a, b))
        graph1.add((b, a))
    m2 = int(lines[2 + m1])
    for line in lines[3 + m1:3 + m1 + m2]:
        a, b = map(int, line.split())
        graph2.add((a, b))
        graph2.add((b, a))
    return graph1, graph2

def find_path(edges, start, end):
    graph = {node: set() for edge in edges for node in edge}
    for a, b in edges:
        graph[a].add(b)
        graph[b].add(a)
    
    queue = deque([(start, [start])])
    seen = {start}
    while queue:
        current, path = queue.popleft()
        if current == end:
            return path
        for next_node in graph[current]:
            if next_node not in seen:
                queue.append((next_node, path + [next_node]))
                seen.add(next_node)
    return []

def add_edge_with_triangles(edges, a, b, graph2):
    path = find_path(edges, a, b)
    if not path:
        print("No path found.")
        return []

    operations = []

    # Dodaj krawędzie tworzące trójkąty wzdłuż ścieżki
    if len(path) % 2 == 0:
        for i in range(0, len(path) - 2, 2):
            new_edge = (path[i], path[i + 2])
            #print(new_edge)
            # Sprawdź, czy nowa krawędź nie istnieje już w grafie
            if new_edge not in edges and (new_edge[1], new_edge[0]) not in edges:
                edges.add(new_edge)
                edges.add((new_edge[1], new_edge[0]))  # Dodawanie w obu kierunkach
                operations.append(f"+ {new_edge[0]} {new_edge[1]}")
    else:
        for i in range(0, len(path) - 2, 2):
            new_edge = (path[i], path[i + 2])
            if new_edge not in edges and (new_edge[1], new_edge[0]) not in edges:
                edges.add(new_edge)
                edges.add((new_edge[1], new_edge[0]))
                #if new_edge in graph2 or (new_edge[1], new_edge[0]) in graph2:
                operations.append(f"+ {new_edge[0]} {new_edge[1]}")

    # Dodaj docelową krawędź jeśli jest potrzebna i nie została jeszcze dodana
    target_edge = (path[0], path[-1])
    if target_edge not in edges and (target_edge[1], target_edge[0]) not in edges and (target_edge in graph2 or (target_edge[1], target_edge[0]) in graph2):
        edges.add(target_edge)
        edges.add((target_edge[1], target_edge[0]))
        operations.append(f"+ {target_edge[0]} {target_edge[1]}")

    return operations

def remove_unnecessary_edges(edges, operations, graph2):
    remove_operations = []
    for op in reversed(operations):  # Przetwarzaj operacje w odwrotnej kolejności
        if op.startswith("+"):
            edge_info = op[2:].split()
            edge = (int(edge_info[0]), int(edge_info[1]))
            # Sprawdź, czy krawędź jest tymczasowa (nie ma jej w docelowym grafie)
            if edge not in graph2 and (edge[1], edge[0]) not in graph2:
                # Usuń krawędź, jeśli jest tymczasowa
                edges.remove(edge)
                edges.remove((edge[1], edge[0]))  # Usuwamy w obu kierunkach
                #print(f"- {edge[0]} {edge[1]}")  # Rejestruj operację usunięcia
                remove_operations.append(f"- {edge[0]} {edge[1]}")

    return remove_operations



def transform_graph(graph1, graph2):
    all_operations = []

    # Dodawanie krawędzi zgodnie z wymaganiami grafu docelowego
    for edge in graph2:
        if edge not in graph1:
            operations = add_edge_with_triangles(graph1, edge[0], edge[1], graph2)
            all_operations.extend(operations)

    remove_operations = remove_unnecessary_edges(graph1, all_operations, graph2)
    all_operations.extend(remove_operations)

    # Remove edges that are not needed
    for edge in list(graph1):
        if edge not in graph2 and (edge[1], edge[0]) not in graph2:
            graph1.remove(edge)
            graph1.discard((edge[1], edge[0]))  # Usuwamy w obu kierunkach, jeśli istnieje
            all_operations.append(f"- {edge[0]} {edge[1]}")

    return all_operations

# Input
# input_str = """
# 6
# 5
# 1 2
# 2 3
# 3 4
# 4 5
# 5 6
# 6
# 1 2
# 2 3
# 3 4
# 4 5
# 5 6
# 6 1
# """
# get input_str fron user
input_str = "" 
n = input()
input_str += n + "\n"
ms = input()
input_str += ms + "\n"
for i in range(int(ms)):
    input_str += input() + "\n"
md = input()
input_str += md + "\n"
for i in range(int(md)):
    input_str += input() + "\n"

graph1_edges, graph2_edges = parse_input(input_str)
operations = transform_graph(graph1_edges, graph2_edges)

# Output
print(len(operations))
for operation in operations:
    print(operation)