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
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> p;
typedef pair<char, p> cp;
int n, m1, m2;
const int lim=30001;
vector <int> gro[lim], gd[lim];
vector<cp> odp;
bool odw[lim];
void wczyt(){
    cin>>n>>m1;
    int a, b;
    for(int i=0; i<m1; i++){
        cin>>a>>b;
        gro[a].push_back(b);
        gro[b].push_back(a);
    }
    cin>>m2;
    for(int i=0; i<m2; i++){
        cin>>a>>b;
        gd[a].push_back(b);
        gd[b].push_back(a);
    }
}

bool znajdzNoweWStarym(int v, int u){
    if(v>u)return true;//v jest mniejsze
    int l=-1, p=gro[v].size()-1, s;
    while(l+1<p){
        s = (l+p)/2;
        if(gro[v][s]<u) l=s;
        else p=s;
    }
    return (gro[v][p]==u);

}
bool znajdzStareWNowym(int v, int u){
    if(v>u) return true;//v jest mniejsze
    /*cout<<"szukam "<<v<<": ";
    for(int i=0; i<gd[v].size(); i++) cout<<gd[v][i]<<" ";
    cout<<endl;*/
    int l=-1, p=gd[v].size()-1, s;
    while(l+1<p){
        s = (l+p)/2;
        if(gd[v][s]<u) l=s;
        else p=s;
    }
    return (gd[v][p]==u || (p>0 && gd[v][p-1]==u));

}
void dodajKraw1(int v){
    odw[v]=true;
    for(int i=0; i<gro[v].size(); i++){
        if(!odw[gro[v][i]]){
            //gro[1].push_back(gro[v][i]);
            //gro[gro[v][i]].push_back(1);
           // cout<<"dodaje? "<<gro[v][i]<<endl;
            if(!znajdzNoweWStarym(1, gro[v][i]) )odp.push_back({'+', {1, gro[v][i]}});
            dodajKraw1(gro[v][i]);
        }
    }
    sort(gro[v].begin(), gro[v].end());
}

void dodajNowe(){//bez jedynki
    for(int i=2; i<=n; i++){
        for(int j=0; j<gd[i].size(); j++) if(gd[i][j]!=1){
            if(!znajdzNoweWStarym(i, gd[i][j])){
                odp.push_back({'+', {i, gd[i][j]}});
            }
        }
    }
}

void usunStare(){//bez jedynki, nie trzeba na prawdę, wystarczy wypisac
  for(int i=2; i<=n; i++){
        for(int j=0; j<gro[i].size(); j++)if(gro[i][j]!=1){
            if(!znajdzStareWNowym(i, gro[i][j])){
                odp.push_back({'-', {i, gro[i][j]}});
            }
        }
    }
}
void usun1(int v){
    //cout<<"usuwam z "<<v<<endl;
    odw[v]=true;
    for(int i=0; i<gd[v].size(); i++){
        if(!odw[gd[v][i]]){
            usun1(gd[v][i]);
        }
    }
    if(v!=1 and !znajdzStareWNowym(1, v)) odp.push_back({'-', {1, v}});
}
void odpowiedz(){
    cout<<odp.size()<<"\n";
    for(int i=0; i<odp.size(); i++){
        cout<<odp[i].first<<" "<<odp[i].second.first<<" "<<odp[i].second.second<<"\n";
    }
}
int main(){
    wczyt();
    /*for(int i=1; i<=n; i++){
        cout<<"\n"<<i<<": ";
        for(int j=0; j<gro[i].size(); j++){
            cout<<gro[i][j]<<" ";
        }
    }*/
    odw[1]=true;
    for(int i=0; i<gro[1].size(); i++){
        dodajKraw1(gro[1][i]);
    }
    sort(gro[1].begin(), gro[1].end());
    dodajNowe();
    usunStare();
    for(int i=1; i<=n; i++){
        odw[i]=false; 
        sort(gd[i].begin(), gd[i].end());
    }
    usun1(1);
    odpowiedz();
   
}