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
#include<bits/stdc++.h>
using namespace std;
const int N = 30008;
int n;
vector<int> odp;
int licznik=0;
vector<int> graph1[N];
vector<int> graph2[N];
struct jededge{
    int odl;
    int ver;
};
bool operator< (jededge a, jededge b){
    if(a.odl<b.odl) return 1;
    if(a.odl>b.odl) return 0;
    if(a.ver<b.ver) return 1;
    return 0;
}
vector<jededge> krok1;
queue<int> bfs;
void step1(int v){
    jededge nowyjededge;
    for(int i=1; i<=n; i++){
        nowyjededge.odl = -1;
        nowyjededge.ver = i;
        krok1.push_back(nowyjededge);
    }
    krok1[v-1].odl=0;
    bfs.push(v);
    while(!bfs.empty()){
        int t = bfs.front();
        bfs.pop();
        for(auto e : graph1[t]){
            if(krok1[e-1].odl==-1){
                krok1[e-1].odl = krok1[t-1].odl+1;
                bfs.push(e);
            }
        }
    }
    sort(krok1.begin(), krok1.end());
    for(auto e : krok1){
        if(e.odl>1){
            licznik++;
            odp.push_back(1);
            odp.push_back(1);
            odp.push_back(e.ver);
        }
    }
}
void step2(int v){
    for(int i=1; i<=n; i++){
        for(int e : graph1[i]){
            if(i!=v&&e!=v&&e>=i){
                licznik++;
                odp.push_back(-1);
                odp.push_back(i);
                odp.push_back(e);
            }
        }
    }
}
void step3(int v){
    for(int i=1; i<=n; i++){
        for(int e : graph2[i]){
            if(i!=v&&e!=v&&e>=i){
                licznik++;
                odp.push_back(1);
                odp.push_back(i);
                odp.push_back(e);
            }
        }
    }
}
vector<jededge> krok4;
void step4(int v){
    jededge nowyjededge;
    for(int i=1; i<=n; i++){
        nowyjededge.odl = -1;
        nowyjededge.ver = i;
        krok4.push_back(nowyjededge);
    }
    krok4[v-1].odl=0;
    bfs.push(v);
    while(!bfs.empty()){
        int t = bfs.front();
        bfs.pop();
        for(auto e : graph2[t]){
            if(krok4[e-1].odl==-1){
                krok4[e-1].odl = krok4[t-1].odl+1;
                bfs.push(e);
            }
        }
    }
    sort(krok4.begin(), krok4.end());
    for(int i=krok4.size(); i>=0; --i){
        auto e = krok4[i];
        if(e.odl>1){
            licznik++;
            odp.push_back(-1);
            odp.push_back(1);
            odp.push_back(e.ver);
        }
    }
}
int main(){
    cin >> n;
    int mone, mtwo;
    cin >> mone;
    int a, b;
    for(int i=0; i<mone; i++){
        cin >> a >> b;
        graph1[a].push_back(b);
        graph1[b].push_back(a);
    }
    cin >> mtwo;
    for(int i=0; i<mtwo; i++){
        cin >> a >> b;
        graph2[a].push_back(b);
        graph2[b].push_back(a);
    }
    step1(1);
    step2(1);
    step3(1);
    step4(1);
    cout << licznik<<"\n";
    for(int i=0; i<odp.size(); i++){
        if(odp[i]==1) cout << "+ ";
        else cout << "- ";
        i++;
        cout << odp[i]<<" ";
        i++;
        cout << odp[i]<<"\n";
    }
}