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
ruchy = 0
odpowiedzKon = ""
class atom:
    def __init__(self, id, polaczenia):
        self.id = id
        self.polaczenia = polaczenia

    def czyIstnieje(self, idPodlaczonej):
        return idPodlaczonej in set(self.polaczenia)

def tworzPolaczenia(sciezka):
    global ruchy, odpowiedzKon
    pomocniczePolaczenia = []
    while len(sciezka) > 2:
        pomocniczePolaczenia.append([sciezka[0],sciezka[2]])
        odpowiedzKon += f"+ {sciezka[0]} {sciezka[2]}\n"
        ruchy += 1
        sciezka.pop(1)

    while len(pomocniczePolaczenia)>1:
        odpowiedzKon += f"- {pomocniczePolaczenia[-2][0]} {pomocniczePolaczenia[-2][1]}\n"
        ruchy += 1
        pomocniczePolaczenia.pop(-2)

def usunPolaczenia(sciezka):
    global ruchy, odpowiedzKon
    pomocniczePolaczenia = []
    while len(sciezka) > 3:
        pomocniczePolaczenia.append([sciezka[0],sciezka[2]])
        odpowiedzKon += f"+ {sciezka[0]} {sciezka[2]}\n"
        ruchy += 1
        sciezka.pop(1)
    ruchy +=1
    odpowiedzKon += f"- {sciezka[0]} {sciezka[-1]}\n"
    while len(pomocniczePolaczenia)>0:
        odpowiedzKon += f"- {pomocniczePolaczenia[-1][0]} {pomocniczePolaczenia[-1][1]}\n"
        ruchy += 1
        pomocniczePolaczenia.pop(-1)
def DFS(start, koniec):
    global czasteczkaStara
    odwiedzone = [start]
    sciezka = [start.id]
    znaleziono = False

    while znaleziono == False:
        znalezionoNowePolaczenie = False
        for i in odwiedzone[-1].polaczenia:
            if i not in sciezka:
                znalezionoNowePolaczenie = True
                nowe = i
                odwiedzone.append(czasteczkaStara[nowe - 1])
                sciezka.append(nowe)
                if koniec.id == nowe:
                    znaleziono = True
                break
        if znalezionoNowePolaczenie == False:
            sciezka.pop()
        else:
            pass
    return sciezka

def generujPolaczeniaDlaAtomu(AtomId, Polaczenia):
    dlaAtomu = []
    for j in Polaczenia:
        if j[0] == AtomId:
            dlaAtomu.append(j[1])
        elif j[1] == AtomId:
            dlaAtomu.append(j[0])
    return atom(AtomId, dlaAtomu)

def czyIstniejeAtomWspolny(atomA, atomB):
    znaleziono = False
    for element in atomA.polaczenia:
        if element in atomB.polaczenia:
            znaleziono = True
            break
    return znaleziono

def tworzPolaczenie(atomA, atomB):
    global odpowiedzKon
    global ruchy
    if czyIstniejeAtomWspolny(atomA, atomB) == True:
        atomA.polaczenia.append(atomB.id)
        atomB.polaczenia.append(atomA.id)
        ruchy += 1
        odpowiedzKon += f"{odpowiedzKon}+ {atomA.id} {atomB.id}\n"
    else:
        sciezka = DFS(atomA, atomB)
        tworzPolaczenia(sciezka)
        atomA.polaczenia.append(atomB.id)
        atomB.polaczenia.append(atomA.id)

def usunPolaczenie(atom1, atom2):
    global ruchy, odpowiedzKon
    if czyIstniejeAtomWspolny(atom1, atom2):
        atom1.polaczenia.remove(atom2.id)
        atom2.polaczenia.remove(atom1.id)
        ruchy += 1
        odpowiedzKon += f"- {atom1.id} {atom2.id}\n"

    else:
        sciezka = DFS(atom1, atom2)
        usunPolaczenia(sciezka)
        atom1.polaczenia.remove(atom2.id)
        atom2.polaczenia.remove(atom1.id)

czasteczkaStara = []
czasteczkaNowa = []

liczbaAtomow = int(input())
liczbaWiazanStara = int(input())
polaczeniaWszystkie = []
for i in range(liczbaWiazanStara):
    input_str = input()
    polaczenie = [int(x) for x in input_str.split()]
    polaczeniaWszystkie.append(polaczenie)
for i in range(1, liczbaAtomow+1):
    czasteczkaStara.append(generujPolaczeniaDlaAtomu(i, polaczeniaWszystkie))

liczbaWiazanNowa = int(input())
polaczeniaWszystkieN = []
for i in range(0,liczbaWiazanNowa):
    input_str = input()
    polaczenie = [int(x) for x in input_str.split()]
    polaczeniaWszystkieN.append(polaczenie)
    if not czasteczkaStara[polaczenie[0]-1].czyIstnieje(polaczenie[1]):
        tworzPolaczenie(czasteczkaStara[polaczenie[0]-1], czasteczkaStara[polaczenie[1]-1])
for i in range(1, liczbaAtomow+1):
    czasteczkaNowa.append(generujPolaczeniaDlaAtomu(i, polaczeniaWszystkie))

def usunDodatkowePolaczenia():
    global ruchy, odpowiedzKon
    for polaczenie in polaczeniaWszystkie:
        if set(polaczenie) not in (set(p) for p in polaczeniaWszystkieN):
            usunPolaczenie(czasteczkaStara[polaczenie[0]-1], czasteczkaStara[polaczenie[1]-1])


usunDodatkowePolaczenia()

print(ruchy)
print(odpowiedzKon)