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
#include<bits/stdc++.h>
using namespace std;
const int MAXN=50007;
int n;
vector<int> graf[MAXN];
vector<int> graf2[MAXN];
bool odw[MAXN];
bool odw2[MAXN];

struct op{
    char typ;
    int a,b;
};

vector<op> operacje;


//dodanie polaczen z 1 do wszystkich innych
void dodaj(int v){
    //if (odw[v]) return;
    queue<pair<int,int>> kol; //wezel,rodzic
    kol.push({v,v});
    //odw[v]=true;
    int s,r;
    while (!kol.empty()){
        v=kol.front().first;
        r=kol.front().second;
        kol.pop();

        if (!odw[v]){ 
            odw[v]=true;
            if (r!=1){
                // cout<<"+ 1 "<<v<<"\n";
                operacje.push_back({'+',1,v});
            }
            for (auto s:graf[v]){ 
                kol.push({s,v});
            }
        }

    }
    return;
}

//Usun wszystkie krwędzie oprócz tych do 1
void usun(int v){
    //if (odw[v]) return;
    for (int i=2;i<=n;i++){
        for (auto e:graf[i]){
            if (e!=1 and e>i){
                // cout<<"- "<<i<<" "<<e<<"\n";
                operacje.push_back({'-',i,e}); 
            }
        }
    }
    return;
}

void dodaj2(int v){
    //if (odw[v]) return;
    for (int i=2;i<=n;i++){
        for (auto e:graf2[i]){
            if (e!=1 and e>i){
                // cout<<"+ "<<i<<" "<<e<<"\n";
                operacje.push_back({'+',i,e}); 
            }
        }
    }
    return;
}

bool poljedynka[MAXN];

void usun2(int v){ 

    odw2[v]=true;
    for (int s:graf2[v]){
        if (!odw2[s]){
            usun2(s);
        }
    }
    if (!poljedynka[v]){ 
        // cout<<"- 1 "<<v<<"\n";
        operacje.push_back({'-',1,v});
    }
    return; 

}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen("input.in", "r", stdin);
    int ma,mb,a,b;
    cin>>n; 
    cin>>ma;

    for(int i=0; i<ma; i++){
        cin>>a>>b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    dodaj(1);
    usun(1);
    cin>>mb;
    poljedynka[1]=true;
    for(int i=0; i<mb; i++){
        cin>>a>>b;
        if (a==1) poljedynka[b]=true;
        if (b==1) poljedynka[a]=true;
        graf2[a].push_back(b);
        graf2[b].push_back(a);
    }
    dodaj2(1);
    usun2(1);
    cout<<operacje.size()<<"\n";
    for (auto e:operacje){
        cout<<e.typ<<" "<<e.a<<" "<<e.b<<"\n";
    }
    //cout<<wyn;
    return 0;
}