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

using namespace std;

void dfs(int v, vector<unordered_set<int>> &edges, vector<bool> &vis, 
    vector<int> &topo) {
    if (vis[v]) return;
    vis[v] = true;

    for (auto &u : edges[v]) {
        if (vis[u]) continue;

        if (edges[0].find(u) == edges[0].end()) {
            topo.push_back(u);
        }
        dfs(u, edges, vis, topo);
    }
}

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


    int n;
    cin >> n;
    
    int ms;
    cin >> ms;
    vector<unordered_set<int>> edges_s(n);
    for (int i = 0; i < ms; ++i) {
        int a, b;
        cin >> a >> b;
        edges_s[a - 1].insert(b - 1);
        edges_s[b - 1].insert(a - 1);
    }

    int md;
    cin >> md;
    vector<unordered_set<int>> edges_d(n);
    for (int i = 0; i < md; ++i) {
        int a, b;
        cin >> a >> b;
        edges_d[a - 1].insert(b - 1);
        edges_d[b - 1].insert(a - 1);
    }

    // add edges to node 0.
    vector<int> topo_add;
    vector<bool> vis_add(n, false);
    dfs(0, edges_s, vis_add, topo_add);

    vector<pair<int, int>> any_erase;
    for (int v = 1; v < n; ++v) {
        for (auto u : edges_s[v]) {
            if (u > v) {
                if (edges_d[v].find(u) == edges_d[v].end()) {
                    // this edge should be erased
                    any_erase.push_back({u, v});
                }
            }
        }
    }

    vector<pair<int, int>> any_add;
    for (int v = 1; v < n; ++v) {
        for (auto u : edges_d[v]) {
            if (u > v) {
                if (edges_s[v].find(u) == edges_s[v].end()) {
                    // this edge should be added
                    any_add.push_back({u, v});
                }
            }
        }
    }

    vector<int> topo_erase;
    vector<bool> vis_erase(n, false);
    dfs(0, edges_d, vis_erase, topo_erase);

    reverse(topo_erase.begin(), topo_erase.end());

    int r = topo_add.size() + any_add.size() + any_erase.size() + topo_erase.size();
    cout << r << "\n";
    // cout << "topo_add\n";
    for (auto v : topo_add) {
        cout << "+ " << 1 << " " << (v + 1) << "\n";
    }
    // cout << "any_add\n";
    for (auto &[u, v] : any_add) {
        cout << "+ " << (u + 1) << " " << (v + 1) << "\n";
    }
    // cout << "any_erase\n";
    for (auto &[u, v] : any_erase) {
        cout << "- " << (u + 1) << " " << (v + 1) << "\n";
    }
    // cout << "topo_erase\n";
    for (auto v : topo_erase) {
        cout << "- " << 1 << " " << (v + 1) << "\n";
    }
}