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
#include<iostream>
#include<vector>
#include<queue>
#include<unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;

struct Obiekt {
    int liczba;
    vector<Obiekt*> sasiedzi;
};
struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& pair) const {
        auto hash1 = hash<T1>{}(pair.first);
        auto hash2 = hash<T2>{}(pair.second);
        return hash1 ^ hash2;
    }
};


vector<int> min_droga(Obiekt& baza, Obiekt& szukana) {
    if (baza.liczba == szukana.liczba) {
        return {};
    }

    queue<Obiekt*> kolejka;
    kolejka.push(&baza);

    unordered_map<int, bool> odwiedzone; // Śledzi odwiedzone wierzchołki
    odwiedzone[baza.liczba] = true;

    unordered_map<int, int> poprzednik; // Śledzi poprzedników na drodze
    poprzednik[baza.liczba] = -1; // -1 oznacza brak poprzednika

    while (!kolejka.empty()) {
        Obiekt* obecny = kolejka.front();
        kolejka.pop();

        if (obecny->liczba == szukana.liczba) {
            vector<int> sciezka;
            for (int at = szukana.liczba; at != -1; at = poprzednik[at]) {
                if( poprzednik[at] != baza.liczba)
                    sciezka.push_back(at);
            }
            reverse(sciezka.begin(), sciezka.end());
            return sciezka;

        }

        for (Obiekt* sasiad : obecny->sasiedzi) {
            if (!odwiedzone[sasiad->liczba]) {
                kolejka.push(sasiad);
                odwiedzone[sasiad->liczba] = true;
                poprzednik[sasiad->liczba] = obecny->liczba;
            }
        }
    }
    return {};
}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int n, k;
    cin >> n >> k;
    vector<Obiekt> T(n+1);
    unordered_set<pair<int,int>,hash_pair> polaczenia;

    for(int i = 1; i <= n; i++) {
        T[i].liczba = i;
    }


    int a, b;
    for(int i = 0; i < k; i++) {
        cin >> a >> b;
        T[a].sasiedzi.push_back(&T[b]);
        T[a].liczba = a;

        T[b].sasiedzi.push_back(&T[a]);
        T[b].liczba = b;

        polaczenia.insert(make_pair(min(a,b),max(a,b)));
    }
    cin >> k;
    int r = 0;

    string output = "";
    for(int i=0;i<k;i++){
        cin>>a>>b;

        auto it = polaczenia.find(make_pair(min(a,b),max(a,b)));

        if (it == polaczenia.end()){
            vector<int> sciezka = min_droga(T[a],T[b]);

            for(int j = 0;j<sciezka.size()-1;j++){
                output+= "+ " + to_string(sciezka[0]) + " " + to_string(sciezka[j+1]) + "\n";
                T[sciezka[0]].sasiedzi.push_back(&T[sciezka[j+1]]);
                T[sciezka[j+1]].sasiedzi.push_back(&T[sciezka[0]]);
            }
            for(int j = 0;j<sciezka.size()-2;j++){
                int c = sciezka[0], d = sciezka[j+1];
                polaczenia.insert(make_pair(min(c,d),max(d,c)));
            }
            r+=  sciezka.size() - 1;

        } else
            polaczenia.erase(it);

    }
    r+=polaczenia.size();
    for(auto pair: polaczenia){
        output+="- " + to_string(pair.second) + " " + to_string(pair.first)+"\n";
    }
    cout<<r<<endl;
    cout<<output;

    return 0;
}