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
#include <bits/stdc++.h>
#define ll long long
#define llu long long unsigned
#define ld long double
#define fr(i,n) for(int i=0;i<n;i++)
#define watch(x) cout<<(#x)<<"=="<<(x)<<endl
#define ft first
#define sc second
#define mp make_pair
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define P 1000000007llu
#define N 30005
#define M 1000001
#define LC 262144
using namespace std;

int getchar_pos_int() {
    int n=0, c=getchar();
    while('0'<=c&&c<='9') {n=n*10+c-'0'; c=getchar();}
    return n;
}

int a, b, n, ms, md, dist[N], parent[N], path[N], pathLen, nToPrint=0;
vi adj[N];
vector<pii> changes, toRemove;
queue<pii> q;
string res;

void bfs(int src, int dst, bool removingVariant) {
    dist[src]=1;
    q.push({1,src});
    while(!q.empty()) {
        auto curr=q.front();
        q.pop();
        for(int v: adj[curr.second]) {
            if(removingVariant&&curr.second==src&&v==dst) continue;
            if(dist[v]<0) {
                q.push({curr.first+1,v});
                dist[v]=curr.first+1;
                parent[v]=curr.second;
            }
        }
    }
}

void constructAccessPathBackward(int src, int dst) {
    int i=0; pathLen=1;
    while(dst!=src) {
        path[i]=dst;
        dst=parent[dst];
        i++, pathLen++;
    }
    path[i]=src;\
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    n=getchar_pos_int(), ms=getchar_pos_int();
    fr(i,ms) {
        a=getchar_pos_int()-1, b=getchar_pos_int()-1;
        adj[a].pb(b); adj[b].pb(a);
    }
    md=getchar_pos_int();
    fr(i,md) {
        a=getchar_pos_int()-1, b=getchar_pos_int()-1;
        changes.pb({a,b});
        fr(j,n) dist[j]=-1;
        bfs(a,b,false);
        constructAccessPathBackward(a,b);
        nToPrint+=max((2*(pathLen-3)+1),0);
        for(int j=2;j<pathLen;j++) res+="+ "+to_string(1+b)+" "+to_string(1+path[j]) +"\n";
        for(int j=2;j<pathLen-1;j++) res+="- "+to_string(1+b)+" "+to_string(1+path[j]) +"\n";
    }
    fr(i,n) {
        for(int v: adj[i]) {
            if(find(changes.begin(),changes.end(),(pii){i,v})==changes.end()
               &&find(changes.begin(),changes.end(),(pii){v,i})==changes.end()) {
                toRemove.pb({i,v});
            }
        }
    }
    for(const auto& change: toRemove) {
        bfs(change.first,change.second,false); constructAccessPathBackward(change.first,change.second);
        nToPrint+=max((2*(pathLen-3)+1),0);
        for(int j=2;j<pathLen-1;j++) res+="+ "+to_string(1+change.second)+" "+to_string(1+path[j]) +"\n";
        res+="- "+to_string(1+change.second)+" "+to_string(1+change.first) +"\n";
        for(int j=2;j<pathLen-1;j++) res+="- "+to_string(1+change.second)+" "+to_string(1+path[j]) +"\n";
    }
    cout<<nToPrint<<'\n'<<res;
    return 0;
}