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
142
143
144
145
146
147
148
149
150
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <set>

void add_atoms(std::vector<std::set<int>> *wiazania, std::set<int> *onesConnected, int atom_do_dodania, std::set<int> *visited){
    visited->insert(atom_do_dodania);
    if(onesConnected->size() == wiazania->size()-1){
        return;
    } else {
        for(const int &atom_number : wiazania->at(atom_do_dodania)){
            if(!visited->contains(atom_number)){
                if(!onesConnected->contains(atom_number)) {
                    std::cout << "+ " << "1 " << atom_number << "\n"; 
                }
                add_atoms(wiazania, onesConnected, atom_number, visited);
            }
        }
    }
}

void remove_atoms_from_1(std::vector<std::set<int>> *wiazania, std::set<int> *to_remove, int atom, std::set<int> *visited){
    visited->insert(atom);
    if(to_remove->size() == 0){
        return;
    } else {
        for(const int &atom_number : wiazania->at(atom)){
            if(!visited->contains(atom_number)){
                remove_atoms_from_1(wiazania, to_remove, atom_number, visited);
                auto pos = to_remove->find(atom_number);
                if(pos != to_remove->end()) {
                    to_remove->erase(pos);
                    std::cout << "- " << atom_number << " " << "1\n";
                }
            }
        }
    }
}

void add_new_connection(std::vector<std::set<int>> *wiazania_do_usuniecia, int a1, int a2){
    auto posa2 = wiazania_do_usuniecia->at(a1).find(a2);
    if(posa2 != wiazania_do_usuniecia->at(a1).end()){
        wiazania_do_usuniecia->at(a1).erase(posa2);//already exist mark not to remove
        auto posa1 = wiazania_do_usuniecia->at(a2).find(a1);
        if(posa2 != wiazania_do_usuniecia->at(a1).end()){
            wiazania_do_usuniecia->at(a2).erase(posa1);//already exist mark not to remove
        }
    } else {
        if (a1 != 1 && a2 != 1){
            std::cout << "+ " << a1 << " " << a2 << "\n";
        }
    }
}

int main() {

    int atomy;
    std::cin >> atomy;

    std::vector<std::set<int>> wiazania_s(atomy + 1);

    int liczba_wiazan_s;
    std::cin >> liczba_wiazan_s;
    for(int i = 0; i < liczba_wiazan_s; i++){
        int a1, a2;
        std::cin >> a1;
        std::cin >> a2;

        wiazania_s.at(a1).insert(a2);
        wiazania_s.at(a2).insert(a1);
    }

    // for(int i = 1; i <= atomy; i++){
    //     for(const int &number : wiazania_s.at(i))
    //         std::cout << number << " ";
    //     std::cout << "\n";
    // }

    std::set<int> initial_1(wiazania_s.at(1));

    // std::cout << "initial_1\n";
    // for(const int &number : initial_1)
    //     std::cout << number << " ";
    // std::cout << "\n";

    std::set<int> visited_insert;
    add_atoms(&wiazania_s, &initial_1, 1, &visited_insert);

    // std::cout << "after_step_1\n";
    // for(int i = 1; i < atomy; i++){
    //     std::cout << i << " - ";
    //     for(const int &number : wiazania_s.at(i))
    //         std::cout << number << " ";
    //     std::cout << "\n";
    // }

    std::vector<std::set<int>> wiazania_p(atomy + 1);
    int liczba_wiazan_p;
    std::cin >> liczba_wiazan_p;
    for(int i = 0; i < liczba_wiazan_p; i++){
        int a1, a2;
        std::cin >> a1;
        std::cin >> a2;

        add_new_connection(&wiazania_s, a1, a2);
        
        wiazania_p.at(a1).insert(a2);        
        wiazania_p.at(a2).insert(a1);
    }

    // std::cout << "after_step_2_s\n";
    // for(int i = 1; i <= atomy; i++){
    //     std::cout << i << " - ";
    //     for(const int &number : wiazania_s.at(i))
    //         std::cout << number << " ";
    //     std::cout << "\n";
    // }

    // std::cout << "after_step_2_p\n";
    // for(int i = 1; i <= atomy; i++){
    //     std::cout << i << " - ";
    //     for(const int &number : wiazania_p.at(i))
    //         std::cout << number << " ";
    //     std::cout << "\n";
    // }

    //remove all except 1
    for(int i = 2; i <= atomy; i++){
        for(const int &number : wiazania_s.at(i))
            if(i > number && i != 1 && number != 1){
                std::cout << "- " << i << " " << number << "\n";
            }
    }


    //remove 1 recursive
    std::set<int> to_remove(wiazania_s.at(1));
    std::set<int> visited;
    remove_atoms_from_1(&wiazania_p, &to_remove, 1, &visited);

    // std::cout << "after_step_3\n";
    // for(int i = 1; i <= atomy; i++){
    //     std::cout << i << " - ";
    //     for(const int &number : wiazania_s.at(i))
    //         std::cout << number << " ";
    //     std::cout << "\n";
    // }
    return 0;    
}