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
129
130
131
132
133
134
135
136
137
138
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>

int n,m1,m2;

struct Edge {
    int u, v;
};


struct Node {
    std::map<int, int> n;
};

struct Event {
    char t;
    int u,v;
};

std::vector<Edge> E;
std::vector<Node> V;
std::set<std::pair<int,int>> sE, dE;
std::vector<Edge> stack;
std::vector<Event> events;

std::pair<int,int> make_e(int a, int b) {
    return {std::min(a,b),std::max(a,b)};
}

void add_edge(int u, int v) {
    if (u > v) std::swap(u,v);
    int e = E.size();
    E.push_back({u,v});
    V[u].n[v] = e;
    V[v].n[u] = e;
}

void remove_edge(int u, int v) {
    V[u].n.erase(v);
    V[v].n.erase(u);
}

void add_t_edge(int u, int v) {
    if (u==v || V[u].n.count(v)) return;
    add_edge(u,v);
    if (dE.count({u,v}) == 0) stack.push_back({u,v});
    events.push_back({'+',u,v});
}

void add_f_edge(int u, int v) {
    if (V[u].n.count(v)) return;
    add_edge(u,v);
    events.push_back({'+',u,v});
}

std::vector<int> find_path(int s, int d) {
    std::deque<int> q;
    std::map<int, int> bt;
    bt[s] = s;
    q.push_back(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop_front();
        if (u == d) break;
        for (auto[v,e] : V[u].n) {
            if (bt.count(v)) continue;
            bt[v] = u;
            q.push_back(v);
        }
    }
    std::vector<int> path = {d};
    while (bt[d] != d) {
        d = bt[d];
        path.push_back(d);
    }
    return path;
}

void construct_bridge(int u, int v) {
    if (u > v) std::swap(u,v);
    auto path = find_path(u, v);
    for (int k=2;k+1<path.size();k*=2) {
        for (int i=0;i<path.size();++i) {
            add_t_edge(path[i], path[std::min(i+k, int(path.size())-1)]);
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin >> n >> m1;
    for (int i=0;i<=n;++i) {
        V.push_back({});
    }
    for (int i=0;i<m1;++i) {
        int a,b;
        std::cin >> a >> b;
        add_edge(a, b);
        sE.insert(make_e(a,b));
    }
    std::cin >> m2;
    for (int i=0;i<m2;++i) {
        int a,b;
        std::cin >> a >> b;
        if (V[a].n.count(b) == 0) {
            construct_bridge(a, b);
            add_f_edge(a, b);
        }
        dE.insert(make_e(a,b));
    }

    for (auto[u, v] : sE) {
        if (dE.count({u,v}) == 1) continue;
        remove_edge(u, v);
    }

    for (auto[u, v] : sE) {
        if (dE.count({u,v}) == 1) continue;
        construct_bridge(u, v);
    }

    for (auto[u, v] : sE) {
        if (dE.count({u,v}) == 1) continue;
        events.push_back({'-',u,v});
    }

    for (auto[u, v] : stack) {
        events.push_back({'-',u,v});
    }

    std::cout << events.size() << "\n";
    for (auto[t,u,v] : events) std::cout << t << " " << u << " " << v << "\n";
    return 0;
}