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

def bfs_path(graf, start, cel):
    odwiedzone = set([start])
    kolejka = deque([(start, [start])])
    while kolejka:
        (current, path) = kolejka.popleft()
        for sasiad in graf[current]:
            if sasiad not in odwiedzone:
                if sasiad == cel:
                    #print(f"Znaleziona ścieżka z {start} do {cel}: {path + [sasiad]}")  # Wypisanie ścieżki
                    return path + [sasiad]
                odwiedzone.add(sasiad)
                kolejka.append((sasiad, path + [sasiad]))
    return []

def main():
    n = int(input())  # Liczba atomów
    ms = int(input())  # Liczba wiązań w cząsteczce początkowej
    graf_poczatkowy = defaultdict(set)
    for _ in range(ms):
        a, b = map(int, input().split())
        graf_poczatkowy[a].add(b)
        graf_poczatkowy[b].add(a)
    
    md = int(input())  # Liczba wiązań w cząsteczce docelowej
    graf_docelowy = defaultdict(set)
    for _ in range(md):
        a, b = map(int, input().split())
        graf_docelowy[a].add(b)
        graf_docelowy[b].add(a)

    ruchy = []
    # Dodaj brakujące połączenia
    for a in range(1, n+1):
        for b in graf_docelowy[a]:
            if b not in graf_poczatkowy[a]:
                sciezka = bfs_path(graf_poczatkowy, a, b)
                # Dla każdego drugiego atomu w ścieżce, zaczynając od trzeciego atomu i kończąc przedostatnim,
                # dodajemy połączenie bezpośrednie z 'a' do tego atomu jako połączenie tymczasowe
                for i in range(2, len(sciezka)-1, 2):
                    if sciezka[i] not in graf_poczatkowy[a]:
                        ruchy.append(f"+ {a} {sciezka[i]}")
                        graf_poczatkowy[a].add(sciezka[i])
                        graf_poczatkowy[sciezka[i]].add(a)
                # Następnie dodajemy połączenie bezpośrednie między 'a' a 'h'
                if b not in graf_poczatkowy[a]:  # Sprawdzamy ponownie, na wypadek gdyby zostało już dodane
                    ruchy.append(f"+ {a} {b}")
                    graf_poczatkowy[a].add(b)
                    graf_poczatkowy[b].add(a)
    
    # Usuń nadmiarowe połączenia
    for a in graf_poczatkowy.keys():
        for b in list(graf_poczatkowy[a]):
            if a not in graf_docelowy[b]:
                ruchy.append(f"- {a} {b}")
                graf_poczatkowy[a].remove(b)
                graf_poczatkowy[b].remove(a)

    print(len(ruchy))
    for ruch in ruchy:
        print(ruch)

# Uruchom główną funkcję, jeśli skrypt jest uruchamiany, a nie importowany
if __name__ == "__main__":
    main()