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
122
123
124
125
126
127
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 1e18 + 7;
const int maxn = 30007;
struct node{
    int v = 0, val = inf;
};
set<pair<int,int>> cel, akt;
set<int> G[maxn];
vector<bool> vist(maxn);
vector<int> ile(maxn), kolejnosc;
const int base = 1 << 15;
vector<node> t(2*base);
void printDodaj(int a, int b){
    cout << "+ " << a << " " << b << "\n";
}

void printUsun(int a, int b){
    cout << "- " << a << " " << b << "\n";
}
void upd(int x, int val){
    x += base;
    t[x].v = x - base;
    t[x].val = val;
    x /= 2;
    while(x){
        if(t[2*x].val < t[2*x + 1].val){
            t[x].val = t[2*x].val;
            t[x].v = t[2*x].v;
        }
        else{
            t[x].val = t[2*x + 1].val;
            t[x].v = t[2*x + 1].v;
        }
        x /= 2;
    }
}
vector<pair<int, pair<int,int>>> res;
int center;
void dfs(int v, int par){
     if(v != center && !G[v].count(center)){
         res.push_back({1, {v,center}});
         G[v].insert(center);
         G[center].insert(v);
         akt.insert({min(center, v), max(center, v)});
     }
     for(int u : G[v]){
         if(u != par && u != center) dfs(u,v);
     }
}
void ustalKol(int v){
     vist[v] = true;
     kolejnosc.push_back(v);
     for(int u : G[v]){
         if(!vist[u] && u != center) ustalKol(u);
     }
}

signed main(){
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    int m1, m2;
    cin >> m2;
    for(int i = 0; i < m2; i++){
        int a,b; cin >> a >> b;
        akt.insert({min(a,b), max(a,b)});
        G[a].insert(b);
        G[b].insert(a);
    }
    cin >> m1;
    for(int i = 0; i < m1; i++){
        int a,b; cin >> a >> b;
        cel.insert({min(a,b), max(a,b)});
    }
    center = 1;
    //zrobienie centrum
    dfs(center, center);

    //dodanie brakujacych
    for(auto [a,b] : cel){
        if(!akt.count({a,b})){
             res.push_back({1, {a,b}});
             G[a].insert(b);
             G[b].insert(a);
             akt.insert({a,b});
         }
     }
    //usuwanie niepotrzebnych niepolacznych z center
    for(int i = 1; i <= n; i++){
        if(i == center) continue;
        for(int u : G[i]){
            if(u != center && !cel.count({min(i, u), max(i,u)})){
                res.push_back({0,{i,u}});
                akt.erase({min(i, u), max(i,u)});
                G[i].erase(u);
                G[u].erase(i);
            }
        }
    }
    for(int i = 1; i <= n; i++) ile[i] = G[i].size() - 1;
    for(int i = 1; i <= n; i++){
        if(i == center) continue;
        if(!vist[i]){
            kolejnosc.clear();
            ustalKol(i);
            for(int u : kolejnosc) upd(u, ile[u]);
            while(t[1].val < inf){
                int u =  t[1].v;
                upd(u, inf);
                if(cel.count({min(u, center), max(u, center)})) continue;
                res.push_back({0,{u, center}});
                G[u].erase(center);
                G[center].erase(u);
                akt.erase({min(u, center), max(u, center)});
                for(int v : G[u]){
                    if(t[v + base].val != inf) upd(v, t[v+base].val-1);
                }
            }
        }
    }
    cout << res.size() << "\n";
    for(auto x : res){
        if(x.first == 1) printDodaj(x.second.first, x.second.second);
        else printUsun(x.second.first, x.second.second);
    }
}