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


def find_shortest_path(graph, start, end):
    dist = defaultdict(list)
    dist[start] = [start]
    q = deque([start])

    while len(q):
        at = q.popleft()
        for next in graph[at]:
            if next not in dist:
                new_path = list(dist[at])
                new_path.append(next)
                dist[next] = new_path
                q.append(next)

    return dist.get(end)


n = int(input())
m_s = int(input())

source_graph = {i+1: set() for i in range(n)}
dest_graph = {i+1: set() for i in range(n)}

add_graph = {}
sub_graph = {}

for i in range(m_s):
    a, b = map(int, input().split())
    source_graph[a].add(b)
    source_graph[b].add(a)

m_d = int(input())

for i in range(m_d):
    c, d = map(int, input().split())
    dest_graph[c].add(d)
    dest_graph[d].add(c)

adds = []
subs = []
for i in range(1, n+1):
    sub_graph[i] = source_graph[i] - dest_graph[i]
    add_graph[i] = dest_graph[i] - source_graph[i]


for i in range(1, n+1):
    for a in sub_graph[i]:
        if (a, i) not in subs:
            subs.append((i, a))

for i in range(1, n+1):
    for a in add_graph[i]:
        if (a, i) not in adds:
            adds.append((i, a))

paths_to_add = []
paths_to_remove = []

for add in adds:
    path = find_shortest_path(source_graph, add[0], add[1])[2:-1]

    path_to_add = []
    for step in path:
        path_to_add.append((add[0], step))
        source_graph[add[0]].add(step)
        source_graph[step].add(add[0])

    path_to_add.append((add[0], add[1]))
    paths_to_add.append(path_to_add)
    source_graph[add[0]].add(add[1])
    source_graph[add[1]].add(add[0])

    paths_to_remove.append([(add[0], step) for step in path])

output = []

for path in paths_to_add:
    for step in path:
        output.append('+ ' + str(step[0]) + ' ' + str(step[1]))

paths_to_remove.reverse()
for path in paths_to_remove:
    for step in path:
        source_graph[step[0]].remove(step[1])
        source_graph[step[1]].remove(step[0])
        output.append('- ' + str(step[0]) + ' ' + str(step[1]))

for sub in subs:
    source_graph[sub[0]].remove(sub[1])
    source_graph[sub[1]].remove(sub[0])

    path = find_shortest_path(source_graph, sub[0], sub[1])[2:-1]
    for step in path:
        output.append('+ ' + str(sub[0]) + ' ' + str(step))

    output.append('- ' + str(sub[0]) + ' ' + str(sub[1]))

    path.reverse()
    for step in path:
        output.append('- ' + str(sub[0]) + ' ' + str(step))

print(len(output))
for o in output:
    print(o)