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

struct elem {
    char c;
    int u, v;
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    // construct source graph
    int ms;
    cin >> ms;

    vector<set<int>> vs(n + 1);
    for (int i = 0, u, v; i < ms; i++) {
        cin >> u >> v;
        vs[u].insert(v);
        vs[v].insert(u);
    }
    
    // construct target graph
    int mt;
    cin >> mt;

    vector<set<int>> vt(n + 1);
    for (int i = 0, u, v; i < mt; i++) {
        cin >> u >> v;
        vt[u].insert(v);
        vt[v].insert(u);
    }

    // list of moves
    vector<elem> moves;
    
    // bfs - create edge from every vertex to vertex 1 in bfs order
    vector<int> que;
    que.push_back(1);

    vector<bool> visited(n + 1);
    visited[1] = true;
    for (int i = 0; i < que.size(); i++) {
        int u = que[i];
        for (int v : vs[u]) {
            if (visited[v] == false) {
                visited[v] = true;
                que.push_back(v);
                if (! vs[1].count(v)) {
                    moves.push_back({'+', 1, v});
                }
            }
        }
    }

    // updating source graph with all necessary edges
    for (elem &e : moves) {
        vs[e.u].insert(e.v);
        vs[e.v].insert(e.u);
    }

    // check target graph add lacking edges to source graph
    for (int u = 1; u <= n; u++) {
        for (int v : vt[u]) {
            if (! vs[u].count(v)) {
                vs[u].insert(v);
                vs[v].insert(u);
                moves.push_back({'+', u, v});
            }
        }
    }
    
    // bfs - create list of vertexes to be removed in reverse bfs order
    que.clear();
    que.push_back(1);

    visited.assign(visited.size(), false);
    visited[1] = true;

    for (int i = 0; i < que.size(); i++) {
        int u = que[i];
        for (int v : vt[u]) {
            if (visited[v] == false) {
                visited[v] = true;
                que.push_back(v);
            }
        }
    }

    // remove extra edges
    for (int u = 2; u <= n; u++) {
        vector<int> lst;
        for (int v : vs[u]) {
            if (v == 1) continue;
            if (! vt[u].count(v)) {
                lst.push_back(v);
                moves.push_back({'-', u, v});
            }            
        }
        for (int v : lst) {
            vs[u].erase(v);
            vs[v].erase(u);
        }
    }

    // remove extra edges travesing prepared list
    for (int i = que.size() - 1; i > 0; i--) {
        int v = que[i];
        if (! vt[1].count(v)) {
            moves.push_back({'-', 1, v});
        }
    }

    // printing results
    cout << moves.size() << "\n";
    for (elem &e : moves) {
        cout << e.c << ' ' << e.u << ' ' << e.v << "\n";
    }
    
    return 0;
}