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
#include <bits/stdc++.h>
using namespace std;
struct Node {
    unordered_set<int> edges;
};
struct Graph {
    int size;
    vector<Node> nodes;
    Graph(int n) { nodes.resize(n + 1); }
    void connect(int a, int b) {
        nodes[a].edges.insert(b);
        nodes[b].edges.insert(a);
    }
    void unlink(int a, int b) {
        nodes[a].edges.erase(b);
        nodes[b].edges.erase(a);
    }
    void read() {
        cin >> size;
        for (int i = 0; i < size; i++) {
            int a, b;
            cin >> a >> b;
            connect(a, b);
        }
    }
};

static vector<int> previous(4096);

vector<int> mkpath(int x, int m1, int m2, int y) {
    vector<int> ret;
    while (m1 != x) {
        ret.push_back(m1);
        m1 = previous[m1];
    }
    ret.push_back(x);
    reverse(ret.begin(), ret.end());
    while (m2 != y) {
        ret.push_back(m2);
        m2 = previous[m2];
    }
    ret.push_back(y);
    return ret;
}

vector<int> bfspath(Graph &d, int x, int y) {
    vector<int> sl(1, x), sr(1, y);
    unordered_set<int> visl{x}, visr{y};
    while (true) {
        vector<int> nsl, nsr;
        for (const auto &a : sl) {
            for (const auto &b : d.nodes[a].edges) {
                if (visl.contains(b)) continue;
                if (visr.contains(b)) return mkpath(x, a, b, y);
                previous[b] = a;
                visl.insert(b);
                nsl.push_back(b);
            }
        }
        for (const auto &a : sr) {
            for (const auto &b : d.nodes[a].edges) {
                if (visr.contains(b)) continue;
                if (visl.contains(b)) return mkpath(x, b, a, y);
                previous[b] = a;
                visr.insert(b);
                nsr.push_back(b);
            }
        }
        sr.swap(nsr);
        nsr.clear();
        sl.swap(nsl);
        nsl.clear();
    }
}

struct Fix {
    int a, b;
    bool revv;
};

static vector<Fix> history;

void stitch(Graph &g, vector<int> &path, bool revv) {
    for (size_t i = 2; i < path.size(); i++) {
        history.push_back({path[0], path[i], revv && i == path.size() - 1});
        g.connect(path[0], path[i]);
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    int n;
    cin >> n;
    Graph gs(n), gd(n);
    gs.read();
    gd.read();
    vector<Fix> fixes;
    for (int a = 1; a <= n; a++) {
        for (const auto &b : gd.nodes[a].edges)
            if (a < b && !gs.nodes[a].edges.contains(b)) fixes.push_back({a, b, false});
        for (const auto &b : gs.nodes[a].edges)
            if (a < b && !gd.nodes[a].edges.contains(b)) fixes.push_back({a, b, true});
    }
    for (const auto &fix : fixes) {
        if (fix.revv) gs.unlink(fix.a, fix.b);
        vector<int> path = bfspath(gs, fix.a, fix.b);
        stitch(gs, path, fix.revv);
    }
    int cnt = 0;
    ostringstream ss;
    for (const auto &fix : history)
        if (!fix.revv) {
            ss << "+ " << fix.a << " " << fix.b << "\n";
            cnt += 1;
        }
    reverse(history.begin(), history.end());
    for (const auto &fix : history)
        if (!gd.nodes[fix.a].edges.contains(fix.b)) {
            ss << "- " << fix.a << " " << fix.b << "\n";
            cnt += 1;
        }
    cout << cnt << endl;
    cout << ss.str();
    return 0;
}