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

using namespace std;

struct T {
    char c;
    int a, b;
    T(char _c, int _a, int _b) : c(_c), a(_a), b(_b) {}
};

vector<T>answer;

void dfs1(int x, vector<set<int>>&adj, vector<bool>&visited) {
    visited[x] = true;
    if(adj[x].find(0) == adj[x].end()) {
        adj[x].insert(0);
        adj[0].insert(x);
        answer.emplace_back('+', 0, x);
    }
    for(int y : adj[x]) {
        if(!visited[y]) {
            dfs1(y, adj, visited);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    int n, ms; cin >> n >> ms;
    
    vector<set<int>>adj(n);
    
    for(int i = 0; i < ms; i++) {
        int a, b; cin >> a >> b; a--; b--;
        adj[a].insert(b);
        adj[b].insert(a);
    }
    
    vector<bool>visited(n, false);
    
    visited[0] = true;
    for(int y : adj[0]) {
        if(!visited[y]) {
            dfs1(y, adj, visited);
        }
    }
    
    for(int i = 1; i < n; i++) {
        for(int j : adj[i]) {
            if(j == 0)
                continue;
            if(j < i) {
                answer.emplace_back('-', i, j);
            }
        }
        adj[i].clear();
    }
    adj[0].clear();
    
    vector<bool>keep(n, false);
    
    int md; cin >> md;
    for(int i = 0;  i < md; i++) {
        int a, b; cin >> a >> b; a--; b--;
        
        if(a != 0 && b != 0) {
            answer.emplace_back('+', a, b);
            adj[a].insert(b);
            adj[b].insert(a);
        } else {
            keep[a] = keep[b] = true;
        }
    }
    keep[0] = true;
    
    vector<int>dist(n, -1);
    queue<int>q;
    dist[0] = 0;
    q.push(0);
    
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        for(int y : adj[x]) {
            if(dist[y] == -1) {
                dist[y] = dist[x] + 1;
                q.push(y);
            }
        }
    }
    
    vector<pair<int, int>>nodes_with_dist;
    for(int i = 0; i < n; i++)
        nodes_with_dist.emplace_back(dist[i], i);
    
    sort(nodes_with_dist.begin(), nodes_with_dist.end());
    
    reverse(nodes_with_dist.begin(), nodes_with_dist.end());
    
    for(auto [d, node] : nodes_with_dist) {
        if(!keep[node]) {
            answer.emplace_back('-', node, 0);
        }
    }
    
    cout << answer.size() << "\n";
    
    for(auto [c, a, b] : answer)
        cout << c << " " << a + 1 << " " << b + 1 << "\n";
    
    
    
    return 0;
}