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

typedef int atom;
typedef std::vector<std::unordered_set<atom>> wiazania;

struct zmiana {
    atom a;
    atom b;
    char znak;
};

void wyznacz_odleglosci(atom z, std::vector<atom> &kolejnosc, wiazania &czasteczka) {
    std::vector<bool> zakolejkowane;

    zakolejkowane.resize(czasteczka.size());
    kolejnosc.clear();
    kolejnosc.reserve(czasteczka.size()-1);
    kolejnosc.push_back(z);
    zakolejkowane[z] = true;

    for (int i = 0; kolejnosc.size() < czasteczka.size()-1; ++i) {
        atom wierzcholek = kolejnosc[i];
        for (atom sasiad: czasteczka[wierzcholek]) {
            if (!zakolejkowane[sasiad]) {
                kolejnosc.push_back(sasiad);
                zakolejkowane[sasiad] = true;
            }
        }
    }
}

void dodaj_mosty(atom z, std::vector<atom> &kolejnosc, wiazania &czasteczka, std::vector<zmiana> &zmiany) {
    for (atom sasiad: kolejnosc) {
        if (sasiad != z && czasteczka[z].find(sasiad) == czasteczka[z].end()) {
            zmiany.emplace_back(z, sasiad, '+');
            czasteczka[z].insert(sasiad);
            czasteczka[sasiad].insert(z);
        }
    }
}

void dodaj_pozadane(wiazania &pozadana, wiazania &czasteczka, std::vector<zmiana> &zmiany) {
    for (int i=1; i<(int)pozadana.size(); ++i) {
        for (atom sasiad: pozadana[i]) {
            if (i < sasiad && czasteczka[i].find(sasiad) == czasteczka[i].end()) {
                zmiany.emplace_back(i, sasiad, '+');
            }
        }
    }
}

void usun_nadmiarowe(wiazania &pozadana, wiazania &czasteczka, std::vector<zmiana> &zmiany) {
    for (int i=1; i<(int)czasteczka.size(); ++i) {
        for (atom sasiad: czasteczka[i]) {
            if (i < sasiad && pozadana[i].find(sasiad) == pozadana[i].end()) {
                zmiany.emplace_back(i, sasiad, '-');
            }
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    wiazania czasteczka;
    wiazania pozadane;
    std::vector<zmiana> zmiany;

    int atomow;
    int wiazan_poczatkowych;
    int wiazan_pozadanych;

    std::cin >> atomow;
    czasteczka.resize(atomow+1);
    pozadane.resize(atomow+1);

    std::cin >> wiazan_poczatkowych;

    atom z;
    atom ku;

    for (int i=0; i<wiazan_poczatkowych; ++i) {
        std::cin >> z >> ku;
        czasteczka[z].insert(ku);
        czasteczka[ku].insert(z);
    }

    std::cin >> wiazan_pozadanych;

    atom korzen = 1;
    std::vector<atom> kolejnosc;
    wyznacz_odleglosci(korzen, kolejnosc, czasteczka);
    dodaj_mosty(korzen, kolejnosc, czasteczka, zmiany);

    for (int i=0; i<wiazan_pozadanych; ++i) {
        std::cin >> z >> ku;
        pozadane[z].insert(ku);
        pozadane[ku].insert(z);
    }
    dodaj_pozadane(pozadane, czasteczka, zmiany);
    usun_nadmiarowe(pozadane, czasteczka, zmiany);

    std::cout << zmiany.size() << "\n";
    for (zmiana &zm: zmiany) {
        std::cout << zm.znak << " " << zm.a << " " << zm.b << "\n";
    }
}