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
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

template<class T> using ordered_set =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;

#define debug(x) cout << "[" <<  #x << " " << x << "] ";

#define ar array
#define ll long long
#define ld long double
#define sz(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()

typedef vector<int> vi;
typedef pair<int,int> pi;

const int MAX_N = 3e4 + 5;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;

unordered_map<int, bool> bajtatom[MAX_N];
unordered_map<int, bool> wantededges[MAX_N];

vector<pi> toremove, toadd;
bool visited[MAX_N];

vector<pi> bfs(int v = 1){
    vector<pi> res;
    queue<int> q;
    q.push(v);
    visited[v] = true;
    while(!q.empty()){
        int u = q.front();
        if(u != 1 && wantededges[1].find(u) == wantededges[1].end()){
            res.push_back({1,u});
        }
        q.pop();
        for(auto it: bajtatom[u]){
            int s = min(u, it.first);
            int e = max(u, it.first);
            if(!visited[it.first] && wantededges[s].find(e) != wantededges[u].end()){
                visited[it.first] = true;
                q.push(it.first);
            }
        }
    }
    reverse(all(res));
    return res;
}

void solve() {
    int n,m1,m2;
    cin >> n >> m1;

    while(m1--){
        int a,b;
        cin >> a >> b;
        bajtatom[a][b] = true;
        bajtatom[b][a] = true;
    }
    cin >> m2;
    while(m2--){
        int a,b;
        cin >> a >> b;
        if(a > b)swap(a,b);
        wantededges[a][b] = true;
    }

    // create super node
    for(int i=2; i<=n; i++){
        if(bajtatom[1].find(i) == bajtatom[1].end()){
            toadd.push_back({1,i});
            bajtatom[1][i] = bajtatom[i][1] = true;
        }
    }

    // add wanted edges
    for(int i=1; i<=n; i++){
        for(auto it: wantededges[i]){
            if(bajtatom[i].find(it.first) == bajtatom[i].end()){
                toadd.push_back({i, it.first});
                bajtatom[i][it.first] = bajtatom[it.first][i] = true;
            }
        }
    }
    
    // upload unwanted edges
    for(int i=2; i<=n; i++){
        for(auto it: bajtatom[i]){
            if(it.first != 1 && it.first > i && wantededges[i].find(it.first) == wantededges[i].end() 
            && wantededges[it.first].find(i) == wantededges[it.first].end()){
                toremove.push_back({i, it.first});
            }
        }
    }

    // remove super edges in correct order
    vector<pi> torem2 =  bfs();

    cout << toremove.size() + toadd.size() + torem2.size() << endl;
    for(pi it: toadd){
        cout << "+ " <<  it.first << " " << it.second << endl;
    }
    for(pi it: toremove){
        cout << "- " <<  it.first << " " << it.second << endl;
    }
    for(pi it: torem2){
        cout << "- " <<  it.first << " " << it.second << endl;
    }

}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int tc = 1;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << t << ": ";
        solve();
    }
}