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
from collections import deque


def main():

    operations = []

    def emit(op, v1, v2):
        operations.append((op, v1, v2))

    n = int(input())

    if n == 2:
        print(0)
        return

    m = int(input())
    graph = {i: set() for i in range(1, n + 1)}
    edges = set()

    for _ in range(m):
        edge = input().split()
        v1, v2 = int(edge[0]), int(edge[1])
        graph[v1].add(v2)
        graph[v2].add(v1)
        edges.add((min(v1, v2), max(v1, v2)))

    dst_m = int(input())
    dst_graph = {i: set() for i in range(1, n + 1)}
    dst_edges = set()

    for _ in range(dst_m):
        edge = input().split()
        v1, v2 = int(edge[0]), int(edge[1])
        dst_graph[v1].add(v2)
        dst_graph[v2].add(v1)
        dst_edges.add((min(v1, v2), max(v1, v2)))

    # len_ = len(edges.intersection(dst_edges))
    # print(f"{len_=}")

    # phase 1: Connect all nodes directly to 1st node using BFS traversal
    visited = set()
    visited.add(1)
    queue = deque()
    for neigh in graph[1]:
        queue.append(neigh)
        visited.add(neigh)

    while queue:
        for _ in range(len(queue)):
            v = queue.popleft()
            for neigh in graph[v]:
                if neigh in visited:
                    continue
                emit("+", 1, neigh)
                queue.append(neigh)
                visited.add(neigh)
                edges.add((1, neigh))

    # phase 2: remove/add edges between any two nodes a and b such a != 1 and b != 1 to be as in dst graph
    # We can do that since any two nodes are connect via node 1
    to_add = dst_edges - edges
    for v1, v2 in to_add:
        if v1 == 1:
            # such edge already been added in 1st phase
            continue
        emit("+", v1, v2)

    to_remove = edges - dst_edges
    to_remove_1st_node = set()
    for v1, v2 in to_remove:
        if v1 == 1:
            # those edges will be removed in 3rd phase
            to_remove_1st_node.add(v2)
        else:
            emit("-", v1, v2)

    # print(edges)
    # print(dst_edges)
    # print(to_add)
    # print(to_remove)
    # print(to_remove_1st_node)

    # phase 3: remove unnecessary edges from node 1 using DFS
    visited = set()
    visited.add(1)
    stack = [1]
    order = []

    while stack:
        # print(stack)
        v = stack.pop()
        order.append(v)
        for neigh in dst_graph[v]:
            if neigh in visited:
                continue
            visited.add(neigh)
            stack.append(neigh)

    # print(order)
    for v in reversed(order):
        if v in to_remove_1st_node:
            emit("-", 1, v)

    # def dfs(v):
    #     # print(f"dfs {v}")
    #     visited.add(v)
    #     for neigh in dst_graph[v]:
    #         if neigh in visited:
    #             continue
    #         dfs(neigh)
    #     if v in to_remove_1st_node:
    #         emit("-", 1, v)
    #
    # dfs(1)

    print(len(operations))
    for op, v1, v2 in operations:
        print(f"{op} {v1} {v2}")


if __name__ == "__main__":
    main()