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

using namespace std;

vector<pair<int, int>> add;
vector<pair<int, int>> del;

void dfsAdd(int u, vector<set<int>> &org, vector<bool> &vis) {
    vis[u] = true;
    if (org[0].count(u) == 0) {
        add.push_back({0, u});
    }
    for (auto v : org[u]) {
        if (!vis[v]) {
            dfsAdd(v, org, vis);
        }
    }
}

void dfsDel(int u, vector<set<int>> &target, vector<bool> &vis) {
    vis[u] = true;
    for (auto v : target[u]) {
        if (!vis[v]) {
            dfsDel(v, target, vis);
        }
    }
    if (target[0].count(u) == 0) {
        del.push_back({0, u});
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<set<int>> org(n);
    vector<set<int>> target(n);
    vector<bool> vis(n);
    int morg;
    cin >> morg;
    for (int i = 0; i < morg; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        org[a].insert(b);
        org[b].insert(a);
    }

    org[0].insert(0);

    dfsAdd(0, org, vis);

    int mtarget;
    cin >> mtarget;
    for (int i = 0; i < mtarget; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        target[a].insert(b);
        target[b].insert(a);
    }

    for (int i = 1; i < n; i++) {
        auto itorg = org[i].begin();
        auto ittarget = target[i].begin();
        while (itorg != org[i].end() && *itorg < i) {
            itorg++;
        }
        while (ittarget != target[i].end() && *ittarget < i) {
            ittarget++;
        }
        while (itorg != org[i].end()) {
            if (ittarget == target[i].end()) {
                del.push_back({i, *itorg});
                itorg++;
            } else if (*ittarget > *itorg) {
                del.push_back({i, *itorg});
                itorg++;
            } else if (*ittarget < *itorg) {
                add.push_back({i, *ittarget});
                ittarget++;
            } else {
                itorg++;
                ittarget++;
            }
        }
        while (ittarget != target[i].end()) {
            add.push_back({i, *ittarget});
            ittarget++;
        }
    }

    fill(vis.begin(), vis.end(), false);
    target[0].insert(0);
    dfsDel(0, target, vis);

    cout << add.size() + del.size() << "\n";
    for (auto &[a, b] : add) {
        cout << "+ " << a + 1 << " " << b + 1 << endl;
    }
    for (auto &[a, b] : del) {
        cout << "- " << a + 1 << " " << b + 1 << endl;
    }
}