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
from collections import defaultdict
import heapq
from copy import deepcopy

e1 = defaultdict(dict)
e2 = defaultdict(dict)
res = []

n = int(input())
m1 = int(input())
for i in range(m1):
    a, b = map(int, input().split())
    e1[a][b] = 1
    e1[b][a] = 1

m2 = int(input())
for i in range(m2):
    a, b = map(int, input().split())
    e2[a][b] = 1
    e2[b][a] = 1

visited = dict()
def dfs(v):
    visited[v] = 1
    if v != 1 and v not in e1[1]:
        res.append(('+', 1, v))
        e1c[1][v] = 1
        e1c[v][1] = 1

    for i in e1[v]:
        if i not in visited:
            dfs(i)

e1c = deepcopy(e1)
dfs(1)
e1 = e1c

for i in range(2, n+1):
    for j in e2[i]:
        if j not in e1[i]:
            res.append(('+', i, j))
            e1[i][j] = 1
            e1[j][i] = 1

e1c = deepcopy(e1)
for i in range(2, n+1):
    for j in e1[i]:
        if j == 1:
            continue
        if j not in e2[i]:
            if i < j:
                res.append(('-', i, j))
            e1c[i].pop(j)
e1 = e1c

nodes = []
seen = {1:1}
for i in range(2, n+1):
    if i not in e2[1]:
        heapq.heappush(nodes, (len(e1[i]), i))
while nodes:
    _, v = heapq.heappop(nodes)
    if v in seen:
        continue
    seen[v] = 1
    res.append(('-', 1, v))

    for i in e1[v]:
        if i in seen or i in e2[1]:
            continue
        e1[i].pop(v)
        heapq.heappush(nodes, (len(e1[i]), i))

print(len(res))
for i in res:
    print(i[0], i[1], i[2])