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
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
int maxn=30003;
vector<vector<int>> v(maxn), vd(maxn);
vector<bool> pj(maxn);
vector<pair<bool, pair<int, int>>> ans;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, p, d;
    cin >> N >> p;
    for (int i=0; i<p; i++){
        int a, b;
        cin >> a >> b;
        if (a>b) swap(a, b);
        if (a==1) pj[b]=true;
        v[b].push_back(a);
        v[a].push_back(b);
    }

    cin >> d;
    vector<pair<int, int>> bp;
    for (int i=0; i<d; i++){
        int a, b;
        cin >> a >> b;
        if (a>b) swap(a, b);
        bool pr=false;
        vd[b].push_back(a);
        vd[a].push_back(b);
        for (int j=0; j<v[a].size(); j++){
            if (v[a][j]==b){
                pr=true;
                break;
            }
        }
        if (!pr && a!=1) bp.push_back({a, b});
    }

    ll inf = 1e9+8;
    vector<ll> dist(N+4, inf);
    dist[1]=0;
    priority_queue<pair<ll, ll>> que;
    que.push({inf, 1});
    while (que.size()>0){
        pair<ll, ll> ww=que.top();
        int u=ww.s;
        que.pop();
        for (int i=0; i<vd[u].size(); i++){
            ll w=vd[u][i];
            if (dist[u]+1<dist[w]){
                dist[w]=dist[u]+1;
                que.push({inf-dist[w], w});
            }
        }
    }
    for (int i=2; i<=N; i++){
        if (!pj[i]){
            v[i].push_back(1);
            v[1].push_back(i);
            ans.push_back({1, {1, i}});
        }
    }
    for (auto i:bp){
        ans.push_back({1, {i.f, i.s}});
    }

    for (int i=2; i<=N; i++){
        for (int j=0; j<v[i].size(); j++){
            int sz=v[i][j];
            if (sz==1 || sz<i) continue;
            // sprawdz czy sz jest w vd
            bool pr=false;
            for (int k=0; k<vd[i].size(); k++){
                if (vd[i][k]==sz){
                    pr=true;
                    break;
                }
            }
            if (!pr){
                ans.push_back({0, {i, sz}});
            }
        }
    }

    vector<int> dous;
    for (int j=0; j<v[1].size(); j++){
        int sz=v[1][j];
        // sprawdz czy sz jest w vd
        bool pr=false;
        for (int k=0; k<vd[1].size(); k++){
            if (vd[1][k]==sz){
                pr=true;
                break;
            }
        }
        if (!pr) dous.push_back(sz);
    }

    vector<pair<int, int>> ds;
    for (auto i:dous){
        ds.push_back({dist[i], i});
    }
    sort(ds.begin(), ds.end(), greater<pair<int, int>>());
    for (auto i:ds){
        ans.push_back({0, {1, i.s}});
    }
    cout << ans.size() << "\n";
    for (auto i:ans){
        if (i.f) cout << "+ ";
        else cout << "- ";
        cout << i.s.f << " " << i.s.s << "\n";
    }
    return 0;
}