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
#include <cstdio>
#include <queue>
#include <set>
#include <algorithm>

void getDepth(int start, const std::vector<std::vector<int> > &edges, std::vector<int> &depth) {
    std::queue<int> q;

    depth.resize(edges.size());
    for (int n=1; n<edges.size(); n++) {
        depth[n] = -1;
    }
    depth[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int n : edges[v]) {
            if (depth[n] == -1) {
                depth[n] = depth[v] + 1;
                q.push(n);
            }
        }
    }
}

void convert(const std::vector<int> &depth, std::vector<std::pair<int, int> > &pairs) {
    for (int i=1; i<depth.size(); ++i) {
        pairs.push_back(std::make_pair(depth[i], i));
    }
}

int main() {
    std::vector<std::vector<int> > source, target;
    std::set<std::pair<int, int > > scheck, tcheck;
    int N;
    int m;

    scanf("%d", &N);
    source.resize(N+1);
    target.resize(N+1);

    scanf("%d", &m);
    for (int i=0; i<m; ++i) {
        int a,b;
        scanf("%d %d", &a, &b);
        source[a].push_back(b);
        source[b].push_back(a);
        scheck.insert(std::make_pair(a, b));
        scheck.insert(std::make_pair(b, a));
    }

    scanf("%d", &m);
    for (int i=0; i<m; ++i) {
        int a,b;
        scanf("%d %d", &a, &b);
        target[a].push_back(b);
        target[b].push_back(a);
        tcheck.insert(std::make_pair(a, b));
        tcheck.insert(std::make_pair(b, a));
    }

    std::vector<int> sdepth;
    std::vector<int> tdepth;
    getDepth(1, source, sdepth);
    getDepth(1, target, tdepth);

    std::vector<std::pair<int, int> > spairs;
    std::vector<std::pair<int, int> > tpairs;
    convert(sdepth, spairs);
    convert(tdepth, tpairs);
    std::sort(spairs.begin(), spairs.end());
    std::sort(tpairs.begin(), tpairs.end(), std::greater<std::pair<int, int> >());

    std::vector<std::pair<int, int> > result1;
    std::vector<std::pair<int, int> > result2;
    for (auto &pair : spairs) {
        if (pair.first > 1) {
            result1.push_back(std::make_pair(1, pair.second));
        }
    }

    for (int v = 2; v <= N; v++) {
        for (int n: target[v]) {
            if (n > v && scheck.find(std::make_pair(v,n)) == scheck.end()) {
                result1.push_back(std::make_pair(v, n));
            }
        }
    }

    for (int v = 2; v <= N; v++) {
        for (int n: source[v]) {
            if (n > v && tcheck.find(std::make_pair(v,n)) == tcheck.end()) {
                result2.push_back(std::make_pair(v, n));
            }
        }
    }

    for (auto &pair : tpairs) {
        if (pair.first > 1) {
            result2.push_back(std::make_pair(1, pair.second));
        }
    }

    printf("%d\n", (int)(result1.size() + result2.size()));
    for (auto p : result1) {
        printf("+ %d %d\n", p.first, p.second);
    }
    for (auto p : result2) {
        printf("- %d %d\n", p.first, p.second);
    }

    return 0;
}