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
128
129
130
131
132
133
134
135
136
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;

struct ans{
    char z;
    int a;
    int b;
};
vector<ans> odp;
bool czy1[30009];
bool del[30009];
bool odw1[30009];
bool odw2[30009];
queue<int>q2;
vector<int>grafp[30009];
queue<int>q1;
set<pair<int,int>> pol;
vector<int>graf[30009];
priority_queue<pair<int,int>>pq;
int odw3[30009];
int odl[30009];
int n;

void bfs2(){
    while(!q2.empty()){
        int x=q2.front();
        int d=0;
        for(int i=0;i<graf[x].size();i++){
            if(!odw2[graf[x][i]]){
                odw2[graf[x][i]]=1;
                q2.push(graf[x][i]);
                d++;
            }
            
        }
        if(d==0){
            pq.push({-1,x});
        }
        q2.pop();
    }
}

void djikstra(){
    int ile=1;
    while(!pq.empty()){
        auto v=pq.top();
        pq.pop();
        if(odw3[v.s]) continue;
        if(!del[v.s])odp.push_back({'-',1,v.s});//cout<<"- 1 "<<v.s<<"\n";
        
        if(ile==n)return;
        ile++;
        odw3[v.s]=true;
        for(auto i:graf[v.s]){
            if(!odw3[i]){
                odl[i]++;
                if(abs(v.f)<=graf[i].size()-odl[i]-1)
                    pq.push({-(graf[i].size()-odl[i]-1),i});
            }
        }
    }
}

void bfs(){
    while(!q1.empty()){
        int x=q1.front();
        for(int i=0;i<grafp[x].size();i++){
            if(!odw1[grafp[x][i]]){
                odw1[grafp[x][i]]=1;
                odp.push_back({'+',1,grafp[x][i]});//cout<<"+ 1 "<<grafp[x][i]<<"\n";
                q1.push(grafp[x][i]);
            }
        }
        q1.pop();
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        if(a>b)swap(a,b);
        grafp[a].push_back(b);
        grafp[b].push_back(a);
        if(a==1){
            czy1[b]=1;
            q1.push(b);
            odw1[b]=1;
            continue;
        }
        pol.insert({a,b});
    }
    odw1[1]=1;
    bfs();
    for(int i=2;i<=n;i++){
        graf[1].push_back(i);
        graf[i].push_back(1);
    }
    int m2;
    cin>>m2;
    for(int i=0;i<m2;i++){
        int a,b;
        cin>>a>>b;
        if(a>b)swap(a,b);
        if(a==1){
            del[b]=1;
            odw2[b]=1;
            q2.push(b);
            continue;
        }
        graf[a].push_back(b);
        graf[b].push_back(a);
        if(pol.find({a,b})!=pol.end()){
            pol.erase(pol.find({a,b}));
            continue;
        }
        odp.push_back({'+',a,b});//cout<<"+ "<<a<<" "<<b<<"\n";
    }
    for(auto i : pol){
        odp.push_back({'-',i.f,i.s});//cout<<"- "<<i.f<<" "<<i.s<<"\n";
    }
    odw2[1]=1;
    bfs2();
    odw3[1]=1;
    djikstra();
    cout<<odp.size()<<"\n";
    for(auto i : odp){
        cout<<i.z<<" "<<i.a<<" "<<i.b<<"\n";
    }
}