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
#include <iostream>
#include <vector>
#include <set>
using namespace std;

#define ROOT 1

void refresh_visited(bool visited[], int n) {
    for (int i = 0; i < n; ++i) {
        visited[i] = false;
    }
}

void dfs_connect(int node, set<int> given[], bool visited[], int n, vector<pair<int, int>> &to_add) {
    if (!visited[node]) {
        visited[node] = true;
        if (node != ROOT && given[node].find(ROOT) == given[node].end()) {
            // cout << "+ 1 " << node << '\n'; 
            to_add.push_back(make_pair(1, node));
            given[node].insert(ROOT);
            given[ROOT].insert(node);
        }

        for (auto it : given[node])
            dfs_connect(it, given, visited, n, to_add);
    }
}

void dfs_disconnect(int node, set<int> desired[], bool visited[], int n, vector<pair<int, int>> &to_remove) {
    if (!visited[node]) {
        visited[node] = true; 

        for (auto it : desired[node])
            dfs_disconnect(it, desired, visited, n, to_remove);

        if (node != ROOT && desired[node].find(ROOT) == desired[node].end()) {
            // cout << "- " << node << " 1 \n";
            to_remove.push_back(make_pair(node, 1));
        }
    }
}

void connect_desired(set<int> given[], set<int> desired[], int n, vector<pair<int, int>> &to_add) {
    for (int i = 1; i < n; ++i) {
        for (auto it : desired[i]) {
            if (given[i].find(it) == given[i].end()) {
                // cout << "+ " << i << " " << it << '\n';
                to_add.push_back(make_pair(i, it));
                given[i].insert(it);
                given[it].insert(i);
            }
        }
    }
}

void disconnect_nondesired(set<int> given[], set<int> desired[], int n, vector<pair<int, int>> &to_remove) {
    for (int i = 2; i < n; ++i) {
        for (auto it : given[i]) {
            if (it != 1 && desired[i].find(it) == desired[i].end()) {
                // cout << "- " << i << " " << it << '\n';
                to_remove.push_back(make_pair(i, it));
                given[i].erase(it);
                given[it].erase(i);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    int n, m;
    cin >> n;
    cin >> m;

    n++;
    set<int> given[n], desired[n];
    
    int a, b;
    for (int i = 0; i < m; ++i) {
        cin >> a >> b;
        given[a].insert(b);
        given[b].insert(a);
    }

    cin >> m;
    for (int i = 0; i < m; ++i) {
        cin >> a >> b;
        desired[a].insert(b);
        desired[b].insert(a);
    }

    // Łączenie wszystkich z 0
    bool visited[n];
    vector<pair<int, int>> to_add, to_remove;

    refresh_visited(visited, n);
    dfs_connect(1, given, visited, n, to_add);

    // Uzupełnianie brakujących krawędzi (tych które są w desired, a nie ma ich w given)
    connect_desired(given, desired, n, to_add);

    // Usuwanie zbędnych krawędzi (tych które są w given, a nie ma ich w desired)
    disconnect_nondesired(given, desired, n, to_remove);

    // Odłączanie od 0
    refresh_visited(visited, n);
    dfs_disconnect(1, desired, visited, n, to_remove);

    cout << to_add.size() + to_remove.size() << '\n';
    for (int i = 0; i < to_add.size(); ++i)
        cout << "+ " << to_add[i].first << " " << to_add[i].second << '\n';

    for (int i = 0; i < to_remove.size(); ++i)
        cout << "- " << to_remove[i].first << " " << to_remove[i].second << '\n';

}