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
#include <stdio.h>
#include <vector>
#include <functional>
#include <queue>
#include <set>
using namespace std;

int N;
vector<vector<int> > G;
int IE;

int K;
vector<vector<int> > solutions;
set<pair<int, int> > input;


vector<int> bfs(int start, int end) {
    queue<vector<int> > Q;
    vector<bool> visited(N+1, false);
    // Mark the current node as visited and enqueue it
    visited[start] = true;
    Q.push({start});

    // Iterate over the queue
    while (!visited[end]) {
        // Dequeue a vertex from queue and print it
        vector<int> currentList = Q.front();
        Q.pop();
        int currentNode = currentList.back();

        for (int neighbor : G[currentNode]) {
            if (neighbor == end) {
                currentList.push_back(neighbor);
                return currentList;
            }
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                vector<int> tlist = currentList;
                tlist.push_back(neighbor);
                Q.push(tlist);
            }
        }
    }
    return {};
}


void build_steps(vector<int> path, vector<vector<int> > & result) {
    int j = path.front();
    for (int a=2;a<path.size();++a) {
        result.push_back({1, j, path[a]});
    }
    for (int a = path.size() - 2;a>1;--a) {
        result.push_back({-1, j, path[a]});
    }
}


int main() {
    scanf("%d",&N);
    G.resize(N+1);
    scanf("%d",&IE);
    for (int i=0;i<IE;++i) {
        int j,k;
        scanf("%d %d",&j,&k);
        G[j].push_back(k);
        G[k].push_back(j);
        input.insert(make_pair(min(j,k), max(j,k)));
    }
    scanf("%d",&K);
    for (int i=0;i<K;++i) {
        int j,k;
        scanf("%d %d",&j,&k);
        input.erase(make_pair(min(j,k), max(j,k)));
        vector<int> path = bfs(j,k);
        if (path.size() == 2) {
            // do nothing
        } else if (path.size() == 3) {
            solutions.push_back({1, j, k});
        } else {
            build_steps(path, solutions);
        }

    }
    
    for(auto x: input) {
        int j = x.first;
        int k = x.second;
        solutions.push_back({-1, j, k});
    }
    // print solutions
    printf("%d\n",solutions.size());
    for (auto sol: solutions) {
        if (sol[0] == 1) {
            printf("+ %d %d\n",sol[1],sol[2]);
        } else {
            printf("- %d %d\n",sol[1], sol[2]);
        }
    }


    return 0;
}