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
# include <bits/stdc++.h>
# define For(i, l, r) for(int i = (l); i <= (r); i++)
# define Rep(i, n) For(i, 0, (n) - 1)
# define size(x) (ll)x.size()
# define MAXSZ 30005
# define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef long double ld;
const ll inf = 1e9 + 7;
const ll mod = 1e9 + 7;
ll n , m1 , m2 , k , q , t , h , w;
vector<vector<ll> >g1(MAXSZ) , g2(MAXSZ);
pair<ll , ll> para(ll u , ll v) {
      if (u > v) swap(u , v);
      return {u , v};
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m1;
    map<pair<ll , ll> , bool>have , need , use;
    Rep (i , m1) {
        ll u , v;
        cin >> u >> v;
        have[para(u , v)] = 1;
        g1[u].push_back(v);
        g1[v].push_back(u);
    }
    cin >> m2;
    vector<pair<ll , ll> >edg;
    Rep (i , m2) {
        ll u , v;
        cin >> u >> v;
        edg.push_back({u , v});
        need[para(u , v)] = 1;
        g2[u].push_back(v);
        g2[v].push_back(u);
    }
    vector<tuple<char , ll , ll> >res;
    ll kol1 = 0;
    {
        vector<ll>d(n + 5 , inf);
        queue<ll>q;
        d[1] = 0;
        q.push(1);
        use.clear();
        while (!q.empty()) {
             ll v = q.front();
             q.pop();
             if (d[v] > 1 && have[para(1 , v)] == 0) {
                  have[para(1 , v)] = 1;
                  res.push_back({'+' , 1 , v});
                  kol1++;
             }
             for (auto to : g1[v]) {
                   if (d[to] > d[v] + 1) {
                        d[to] = d[v] + 1;
                        q.push(to);
                   }
             }
        }
    }
    ll kol2 = 0;
    for (auto [u , v] : edg) {
         if (have[para(u , v)] == 0) {
              res.push_back({'+' , u , v});
              have[para(u , v)] = 1;
              kol2++;
         }
    }
    ll kol3 = 0;
    vector<pair<ll , ll> >v_use;
    {
        vector<ll>d(n + 5 , inf);
        queue<ll>q;
        d[2] = 0;
        q.push(2);
        use.clear();
        while (!q.empty()) {
             ll v = q.front();
             q.pop();
             if (d[v] > 1 && have[para(2 , v)] == 0) {
                  have[para(2 , v)] = 1;
                  res.push_back({'+' , 2 , v});
                  use[para(2 , v)] = 1;
                  v_use.push_back({2 , v});
                  kol3++;
             }
             for (auto to : g2[v]) {
                   if (d[to] > d[v] + 1) {
                        d[to] = d[v] + 1;
                        q.push(to);
                   }
             }
        }
    }
    for (auto [par , cnt] : have) {
         if (!cnt || need[par] || use[par]) continue;
         res.push_back({'-' , par.first , par.second});
    }
    reverse(all(v_use));
    for (auto [u , v] : v_use) {
          res.push_back({'-' , u , v});
    }
    cout << size(res) << "\n";
    for (auto [c , u , v] : res) {
         cout << c << ' ' << u << ' ' << v << "\n";
    }
}
//odjgoadfhfoav hash1 i hash2 (hash1 * 1e9 + hash