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

set<pair<int, int>> readGraph() {
    int m;
    cin >> m;
    set<pair<int, int>> g;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        g.insert({min(a, b), max(a, b)});
    }
    return g;
}
vector<vector<int>> graphToAdjList(const auto &graph, int n) {
    vector<vector<int>> adj;
    adj.resize(n + 1);
    for (auto &k : graph) {
        adj[k.first].push_back(k.second);
        adj[k.second].push_back(k.first);
    }
    return adj;
}

pair<int, int> makeEdge(int a, int b) {
    return {min(a, b), max(a, b)};
}

char buf[32];
string getOp(char s, int e1, int e2) {
    snprintf(buf, 30, "%c %d %d", s, e1, e2);
    return string(buf);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    auto g1 = readGraph();
    auto g2 = readGraph();
    vector<string> ops;

    set<pair<int, int>> toAdd;
    ranges::set_difference(g2, g1, inserter(toAdd, end(toAdd)));
    int magicNode = 1;
    {
        auto adj = graphToAdjList(g1, n);
        vector<int> visited;
        visited.resize(n + 1, 0);
        queue<int> bfs;
        bfs.push(magicNode);
        visited[magicNode] = 1;
        while (!bfs.empty()) {
            int node = bfs.front();
            bfs.pop();
            for (auto e : adj[node]) {
                auto edge = makeEdge(magicNode, e);
                if (!visited[e]) {
                    bfs.push(e);
                    visited[e] = 1;
                    if (!g1.contains(edge)) {
                        ops.push_back(getOp('+', magicNode, e));
                        g1.insert(edge);
                        toAdd.erase(edge);
                    }
                }
            }
        }
    }
    for (auto e : toAdd) {
        ops.push_back(getOp('+', e.first, e.second));
        g1.insert(e);
    }
    set<pair<int, int>> toRemove;
    set<int> rootToRemove;
    ranges::set_difference(g1, g2, inserter(toRemove, end(toRemove)));
    for (auto e : toRemove) {
        if (e.first != magicNode && e.second != magicNode) {
            ops.push_back(getOp('-', e.first, e.second));
            g1.erase(e);
        } else {
            rootToRemove.insert(e.first != magicNode ? e.first : e.second);
        }
    }
    {
        auto adj = graphToAdjList(g2, n);
        vector<int> visited;
        visited.resize(n + 1, 0);
        queue<int> bfs;
        bfs.push(magicNode);
        visited[magicNode] = 1;
        vector<int> toRemoveSorted;
        toRemoveSorted.reserve(size(rootToRemove));
        while (!bfs.empty()) {
            int node = bfs.front();
            bfs.pop();
            for (auto e : adj[node]) {
                if (!visited[e]) {
                    bfs.push(e);
                    visited[e] = 1;
                    if (rootToRemove.contains(e)) {
                        toRemoveSorted.push_back(e);
                    }
                }
            }
        }
        for (auto iter = rbegin(toRemoveSorted); iter != rend(toRemoveSorted); ++iter) {
            ops.push_back(getOp('-', magicNode, *iter));
        }
    }
    cout << size(ops) << '\n';
    for (auto &s : ops) {
        cout << s << '\n';
    }
}