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
#include <bits/stdc++.h>

#define ndl '\n'
#define ll long long
#define INF 1000000007
#define st first
#define nd second
#define debug(x) cout << #x << ": " << x << ndl
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin(), (x).end()

using namespace std;

struct pair_hash {
    inline std::size_t operator()(const std::pair<int,int> & v) const {
        return v.first*31+v.second;
    }
};

void bfs(int v, vector<int> &dist, vector<vector<int>> &G) {
    fill(dist.begin(), dist.end(), 0);
    queue<int> q;
    q.push(v);
    dist[v] = 1;
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for(auto x: G[v]) 
            if(dist[x] == 0) {
                dist[x] = dist[v] + 1;
                q.push(x);
            }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin>>n;
    unordered_set<pair<int, int>, pair_hash> czy_krawedz, czy_docelowa_krawedz;
    vector<vector<int>> G(n+1), GD(n+1);
    vector<string> output_arr;

    {
        int m,a,b; cin>>m;
        for(int i=0;i<m;i++) {
            cin>>a>>b;
            G[a].push_back(b);
            G[b].push_back(a);
            czy_krawedz.insert({min(a, b), max(a, b)});
        }
    }

    vector<pair<int,int>> krawedzie_do_dodania, krawedzie_do_usuniecia;

    {
        int m,a,b; cin>>m;
        for(int i=0;i<m;i++) {
            cin>>a>>b;
            GD[a].push_back(b);
            GD[b].push_back(a);
            czy_docelowa_krawedz.insert({min(a, b), max(a, b)});
            if(!czy_krawedz.count({min(a, b), max(a, b)}))
                krawedzie_do_dodania.push_back({min(a, b), max(a, b)});
        }
    }

    for(auto x:czy_krawedz) 
        if(!czy_docelowa_krawedz.count(x))
            krawedzie_do_usuniecia.push_back(x);

    vector<int> disG(n+1), disGD(n+1);

    bfs(1, disG, G);
    bfs(1, disGD, GD);

    vector<pair<int,int>> A;
    for(int i=1;i<=n;i++) 
        A.push_back({disG[i], i});
    
    std::sort(A.begin(), A.end());
    for(auto [a,b]:A) {
        if(a<3) continue;
        if(!czy_krawedz.count({1, b})) {
            output_arr.push_back("+ "+to_string(1)+" "+to_string(b));
            czy_krawedz.insert({1, b});
        }
    }

    for(auto x:krawedzie_do_dodania) 
        if(!czy_krawedz.count(x)) {
            output_arr.push_back("+ "+to_string(x.first)+" "+to_string(x.second));
            czy_krawedz.insert(x);
        }
    
    for(auto x:krawedzie_do_usuniecia) { // pamietac o tych jedynkach???
        if(czy_krawedz.count(x)) {
            output_arr.push_back("- "+to_string(x.first)+" "+to_string(x.second));
            czy_krawedz.erase(x);
        }
    }

    A.clear();
    for(int i=1;i<=n;i++) 
        A.push_back({disGD[i], i});
    
    sort(A.rbegin(), A.rend());
    for(auto [a,b]:A) {
        if(a > 2 && czy_krawedz.count({1, b}) && !czy_docelowa_krawedz.count({1, b})) {
            output_arr.push_back("- "+to_string(1)+" "+to_string(b));
            czy_krawedz.erase({1, b});
        }
    }

    cout<<output_arr.size()<<"\n";
    for(auto x:output_arr) cout<<x<<"\n";
}