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 <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#define pb emplace_back
#define ins insert
#define mp make_pair
#define ssize(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pld pair <ld, ld>
#define st first
#define nd second

using namespace std;
using ll = int_fast64_t;
// using lll = __int128_t;
using ld = long double;
const int oo = 1e9 + 7;
const ll ool = 1e18;
const int mod = 1e9 + 7;

void solve(){
    int n; cin >> n;
    vector <vector<int>> gst(n);
    int ms; cin >> ms;
    set <pii> rn;
    while(ms --){
        int a, b; cin >> a >> b;
        -- a; -- b;
        gst[a].pb(b);
        gst[b].pb(a);
        if(a > b) swap(a, b);
        rn.ins(mp(a, b));
    }
    vector <int> d(n);
    vector <bool> vis(n);
    queue <int> q;
    q.emplace(0);
    vis[0] = 1;
    while(ssize(q)){
        int v = q.front();
        q.pop();
        for(auto u: gst[v]){
            if(!vis[u]){
                vis[u] = 1;
                d[u] = d[v] + 1;
                q.emplace(u);
            }
        }
    }
    vector <pii> td;
    for(int i = 1; i < n; i ++) td.pb(d[i], i);
    sort(all(td));
    vector <pair<char, pii>> ans;
    for(auto [x, v]: td){
        if(rn.find(mp(0, v)) == rn.end()){
            rn.ins(mp(0, v));
            ans.pb(mp('+', mp(0, v)));
        }
    }
    int md; cin >> md;
    set <pii> need;
    vector <vector<int>> g(n);
    while(md --){
        int a, b; cin >> a >> b;
        -- a; -- b;
        if(a > b) swap(a, b);
        g[a].pb(b);
        g[b].pb(a);
        need.ins(mp(a, b));
        if(rn.find(mp(a, b)) == rn.end()){
            ans.pb(mp('+', mp(a, b)));
            rn.ins(mp(a, b));
        }
    }
    for(auto [a, b]: rn){
        if(!a || !b) continue;
        if(need.find(mp(a, b)) == need.end()){
            ans.pb(mp('-', mp(a, b)));
        }
    }
    fill(all(vis), 0);
    fill(all(d), 0);
    td.clear();
    q.emplace(0);
    vis[0] = 1;
    while(ssize(q)){
        int v = q.front();
        q.pop();
        for(auto u: g[v]){
            if(!vis[u]){
                vis[u] = 1;
                d[u] = d[v] + 1;
                q.emplace(u);
            }
        }
    }
    for(int i = 0; i < n; i ++) td.pb(d[i], i);
    sort(rall(td));
    for(auto [x, v]: td){
        if(d[v] >= 2){
            ans.pb(mp('-', mp(0, v)));
        }
    }
    cout << ssize(ans) << '\n';
    for(auto [c, e]: ans){
        cout << c << ' ' << e.st + 1 << ' ' << e.nd + 1 << '\n';
    }
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t; t = 1;
    // cin >> t;
    while(t --) solve();
    return 0;
}