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
#include <bits/stdc++.h>

using std::cin, std::cout;
using std::string;
using std::array;
using std::vector;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
const char endl = '\n';

template<class num>
inline num ceildiv(num a, num b) { return (a + b - 1) / b; }

template<class num>
inline num modulo(num i, num n) { //return value >= 0
    const num k = i % n;
    return k < 0 ? k + n : k;
}

const int max_n = 30000 + 5;

vector<int> pre_conns[max_n];
vector<int> post_conns[max_n];

std::set<std::pair<int, int>> pre_edges, post_edges;

vector<std::pair<int, int>> network_additions, network_deletions, additions, deletions;

int main() {
    std::ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    int n, pre_edge_count;
    cin >> n >> pre_edge_count;

    for (int i = 0; i < pre_edge_count; i++) {
        int a, b;
        cin >> a >> b;
        if (a > b) std::swap(a, b);

        pre_conns[a].push_back(b);
        pre_conns[b].push_back(a);

        if (a != 1) pre_edges.insert({a, b}); // if it is connected to [1] it is going to be handled by the network
    }            

    // make everything point to [1]
    {
        vector<int> to_visit; // they are connected but not their children
        bool checked[max_n]{}; // they are registered in network_additions
        checked[1] = true;

        // we don't want to connect the ones that already are
        for (int conn : pre_conns[1]) {
            checked[conn] = true;
            to_visit.push_back(conn);
        }

        while (not to_visit.empty()) {
            int curr = to_visit.end()[-1];
            to_visit.pop_back();

            for (int conn : pre_conns[curr]) {
                if (not checked[conn]) {
                    checked[conn] = true;
                    to_visit.push_back(conn);
                    network_additions.emplace_back(1, conn);
                }
            }
        }
    }


    int post_edge_count;
    cin >> post_edge_count;

    for (int i = 0; i < post_edge_count; i++)  {
        int a, b;
        cin >> a >> b;
        if (a > b) std::swap(a, b);

        post_conns[a].push_back(b);
        post_conns[b].push_back(a);

        if (a != 1) post_edges.insert({a, b}); // if it is connected to [1] it is going to be handled by the network
    }

    // delete everything unneccesarily pointed to [1]
    {
        vector<int> to_visit; // they are connected but not their children
        bool checked[max_n]{}; // they are registered in network_deletions
        checked[1] = true;

        // we don't want to connect the ones that already are
        for (int conn : post_conns[1]) {
            checked[conn] = true;
            to_visit.push_back(conn);
        }

        while (not to_visit.empty()) {
            int curr = to_visit.end()[-1];
            to_visit.pop_back();

            for (int conn : post_conns[curr]) {
                if (not checked[conn]) {
                    checked[conn] = true;
                    to_visit.push_back(conn);
                    network_deletions.emplace_back(1, conn);
                }
            }
        }

        std::ranges::reverse(network_deletions); // because we want to delete from furthest to closest
    }


    // if they disappeared, they go to deletions
    std::ranges::set_difference(pre_edges, post_edges, std::back_inserter(deletions)); 

    // if they appeared, they go to additions
    std::ranges::set_difference(post_edges, pre_edges, std::back_inserter(additions)); 

    // print results

    for (auto [a, b] : network_additions) {
        cout << '+' << a << ' ' << b << endl;
    }

    for (auto [a, b] : additions) {
        cout << '+' << a << ' ' << b << endl;
    }

    for (auto [a, b] : deletions) {
        cout << '-' << a << ' ' << b << endl;
    }

    for (auto [a, b] : network_deletions) {
        cout << '-' << a << ' ' << b << endl;
    }

    cout << endl;
    return 0;
}