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
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define ll long long


const ll maxn = 1e5 + 7;
int n, m1, m2, a, b, licz;
vector<int> G1[maxn], G2[maxn];
vector<pair<int, int>> edg, usu;
bool vis[maxn], ones[maxn];
pair<int, int> dist[maxn];
queue<pair<int, int>> q;

void zeruj(int kon){
    for(int i = 1; i <= kon; i++){
        vis[i] = 0;
        dist[i].st = INT_MAX;
        dist[i].nd = i;
    }
    return;
}

void BFS(int w, int odl){
    q.push({w, odl});
    vis[w] = 1;
    while(!q.empty()){
        w = q.front().st;
        odl = q.front().nd;
        
        q.pop();
        for(int i = 0; i < G1[w].size(); i++){
            if(!vis[G1[w][i]]){
                vis[G1[w][i]] = 1;
                if(odl >= 1){
                    licz++;
                    edg.push_back({1, G1[w][i]});
                }
                q.push({G1[w][i], odl + 1});
            }
        }
    }
}

void BFS2(int w, int odl){
    q.push({w, odl});
    while(!q.empty()){
        w = q.front().st;
        odl = q.front().nd;
        dist[w].st = min(dist[w].st, odl);
        
        q.pop();
        for(int i = 0; i < G2[w].size(); i++){
            if(!vis[G2[w][i]]){
                vis[G2[w][i]] = 1;
                q.push({G2[w][i], odl + 1});
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m1;
    for(int i = 1; i <= m1; i++){
        cin >> a >> b;
        G1[a].push_back(b);
        G1[b].push_back(a);
        if(a == 1 || b == 1){
            continue;
        }
        else{
            licz++;
            usu.push_back({-a, b});
            // edg.push_back({-a, b});
        }     
    }
    BFS(1, 0);
    for(int i = 0; i < usu.size(); i++)
        edg.push_back(usu[i]);
    cin >> m2;
    for(int i = 1; i <= m2; i++){
        cin >> a >> b;
        G2[a].push_back(b);
        G2[b].push_back(a);
        if(a == 1 || b == 1){
            if(a > b)
                swap(a, b);
            ones[b] = 1;
        }
        else{
            licz++;
            edg.push_back({a, b});
        }
    }
    // cout << '\n';
    zeruj(n);
    BFS2(1, 0);
    sort(dist + 1, dist + n + 1);
    for(int i = n; i > 1; i--){
        if(ones[dist[i].nd] == 0){
            licz++;
            edg.push_back({-1, dist[i].nd});
        }
    }
    // cout << '\n';
    cout << licz << '\n';
    for(int i = 0; i < edg.size(); i++){
        if(edg[i].st > 0)
            cout << "+ " << edg[i].st << " " << edg[i].nd << '\n';
        else
            cout << "- " << -edg[i].st << " " << edg[i].nd << '\n';
    }
}