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
#include <bits/stdc++.h>
#define mp make_pair
#define f first
#define s second
#define pb emplace_back
#define FOR(i,a,b) for(int i = a; i < b;++i)
using namespace std;
const int maxn = 30 * 1000 + 5;
vector<int> V[maxn],V1[maxn],V2[maxn];
vector<pair<int,int>> kraw1,kraw2,kraw3;
vector<pair<int,pair<int,int>>> ans,ans1;
map<pair<int,int>,int> mapa,mapa1;
int sto[maxn],vis[maxn],k;
inline void dfs(int v){
    for(auto &y : V[v]){
        if(vis[y] == 0){
            vis[y] = 1;
            if(y != k || v != k){
                int k1 = k, y1 = y;
                if(k1 > y1){
                    swap(k1,y1);
                }
                if(mapa[mp(k1,y1)] == 0){
                    ans.pb(mp(1,mp(k1,y1)));
                    kraw3.pb(mp(k1,y1));
                    mapa[mp(k1,y1)] = 1;
                }
            }
            dfs(y);
        }
    }
}
inline void dfs1(int v){
    for(auto &y : V1[v]){
        if(vis[y] == 0){
            vis[y] = 1;
            if(y != k || v != k){
                int k1 = k, y1 = y;
                if(k1 > y1){
                    swap(k1,y1);
                }
                if(mapa1[mp(k1,y1)] == 0){
                    ans1.pb(mp(-1,mp(k1,y1)));
                    mapa1[mp(k1,y1)] = 1;
                }
                if(mapa[mp(k1,y1)] == 0){
                    mapa[mp(k1,y1)] = 1;
                    ans.pb(mp(1,mp(k1,y1)));
                }
            }
            dfs1(y);
        }
    }
}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n,m,m1;
    cin>>n >>m;
    FOR(i,0,m){
        int x,y;
        cin>>x >>y;
        if(x > y){
            swap(x,y);
        }
        V[x].pb(y);
        V[y].pb(x);
        V2[x].pb(y);
        V2[y].pb(x);
        kraw3.pb(mp(x,y));
        ++mapa[mp(x,y)];
    }
    cin>>m1;
    FOR(i,0,m1){
        int x,y;
        cin>>x >>y;
        if(x > y){
            swap(x,y);
        }
        V1[x].pb(y);
        V1[y].pb(x);
        kraw2.pb(mp(x,y));
        if(mapa[mp(x,y)] == 0){
            kraw1.pb(mp(x,y));
            ++sto[x];
            ++sto[y];
        }
    }
    k = 1;
    FOR(i,1,n + 1){
        if(sto[k] < sto[i]){
            k = i;
        }
    }
    vis[k] = 1;
    dfs(k);
    for(auto &y : kraw1){
        if(mapa[mp(y.f,y.s)] == 0){
            ans.pb(mp(1,mp(y.f,y.s)));
            kraw3.pb(mp(y.f,y.s));
            mapa[mp(y.f,y.s)] = 1;
        }
    }
    FOR(i,0, n + 1){
        vis[i] = 0;
        sto[i] = 0;
    }
    for(auto &y : kraw2){
        mapa1[mp(y.f,y.s)] = 1;
    }
    for(auto &y : kraw3){
        if(mapa1[mp(y.f,y.s)] == 0){
            ++sto[y.f];
            ++sto[y.s];
        }
    }
    vis[k] = 1;
    dfs1(k);
    for(auto &y : kraw3){
        if(mapa1[mp(y.f,y.s)] == 0){
            ans1.pb(mp(-1,mp(y.f,y.s)));
            mapa1[mp(y.f,y.s)] = 1;
        }
    }
    reverse(ans1.begin(),ans1.end());
    cout<<ans.size() + ans1.size() <<"\n";
    for(auto y : ans){
        cout<<"+ " <<y.s.f <<" " <<y.s.s <<"\n";
    }
    for(auto y : ans1){
        cout<<"- " <<y.s.f <<" " <<y.s.s <<"\n";
    }
}