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

struct move {
    char symbol;
    int u;
    int v;

    move(const char& symbol, const int& u, const int& v) : symbol(symbol), u(u), v(v) {}

    move() {}
};

void get_shortest_path(const std::vector<std::vector<int>>& G, int n, int s, int t, std::vector<int>& result) {
    std::queue<int> Q;
    std::vector<int> paths(n, -1);
    paths[t] = -2;
    Q.push(t);
    while(true) {
        int u = Q.front();
        Q.pop();
        if(u == s) {
            break;
        }

        for(auto v : G[u]) {
            if(paths[v] == -1) {
                paths[v] = u;
                Q.push(v);
            }
        }
    }

    int current = s;
    do {
        result.push_back(current);
        current = paths[current];
    } while(current != -2);
}

int main() {
    std::ios_base::sync_with_stdio(0);
    int n;
    std::cin >> n;
    int m1, m2;
    std::cin >> m1;
    std::vector<std::vector<int>> source(n);
    for(int i = 0; i < m1; ++i) {
        int a, b;
        std::cin >> a >> b;
        source[a - 1].push_back(b - 1);
        source[b - 1].push_back(a - 1);
    }
    std::cin >> m2;
    std::vector<std::pair<int, int>> target_edges(m2);
    std::vector<move> moves;
    for(int i = 0; i < m2; ++i) {
        int a, b;
        std::cin >> a >> b;
        if(a > b) {
            std::swap(a, b);
        }
        --a;
        --b;
        std::vector<int> shortest_path;
        get_shortest_path(source, n, a, b, shortest_path);
        for(int i = 2; i < shortest_path.size(); ++i) {
            source[shortest_path[0]].push_back(shortest_path[i]);
            source[shortest_path[i]].push_back(shortest_path[0]);
            moves.push_back({'+', shortest_path[0], shortest_path[i]});
        }
        target_edges.push_back({a, b});
    }
    std::sort(target_edges.begin(), target_edges.end());
    std::queue<std::pair<int, int>> edges_to_remove;
    for(int u = 0; u < n; ++u) {
        for(auto v : source[u]) {
            if(u > v) {
                continue;
            }
            auto edge = std::make_pair(u, v);
            if(!std::binary_search(target_edges.begin(), target_edges.end(), edge)) {
                edges_to_remove.push(edge);
            }
        }
    }

    while(!edges_to_remove.empty()) {
        auto edge = edges_to_remove.front();
        edges_to_remove.pop();
        source[edge.first].erase(std::find(source[edge.first].begin(), source[edge.first].end(), edge.second));
        source[edge.second].erase(std::find(source[edge.second].begin(), source[edge.second].end(), edge.first));

        std::vector<int> shortest_path;
        get_shortest_path(source, n, edge.first, edge.second, shortest_path);
        for(int i = 2; i < shortest_path.size() - 1; ++i) {
            source[shortest_path[0]].push_back(shortest_path[i]);
            source[shortest_path[i]].push_back(shortest_path[0]);
            moves.push_back({'+', shortest_path[0], shortest_path[i]});
        }
        for(int i = shortest_path.size() - 2; i >= 2; --i) {
            edges_to_remove.push({shortest_path[0], shortest_path[i]});
        }
        moves.push_back({'-', edge.first, edge.second});
    }
    std::cout << moves.size() << "\n";
    for(auto move : moves) {
        std::cout << move.symbol << " " << move.u + 1 << " " << move.v + 1 << "\n";
    }
}