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<bits/stdc++.h>

#define FOR(i,s,e) for(int i=(s); i<=(e); i++)
#define FORD(i,s,e) for(int i=(s); i>=(e); i--)
#define ALL(k) (k).begin(), (k).end()
#define e1 first
#define e2 second
#define mp make_pair
 
using namespace std;
using LL=long long;
using LD=long double;
using PII=pair<int,int>;
const int MAXN = 30111;

vector<int> initial_edges[MAXN];
vector<int> final_edges[MAXN];

vector<pair<char, PII>> moves;


int vis[MAXN];
vector<int> dfs_order;
void dfs(int v, bool use_initial_edges=true){
    dfs_order.push_back(v);
    auto edges = use_initial_edges ? &(initial_edges) : &(final_edges);
    for (auto &b: (*edges)[v]){
        if (!vis[b]){
            vis[b] = 1;
            dfs(b);
        }
    }
}


int main(){
    int n; scanf("%d",&n);
    int ms; scanf("%d", &ms);
    set<PII> existing_edges;
    FOR(i,1,ms){
        int a, b; scanf("%d%d", &a,&b);
        if (a > b){
            swap(a,b);
        }
        // printf("Initial edge %d %d\n", a,b);
        initial_edges[a].push_back(b);
        initial_edges[b].push_back(a);
        existing_edges.insert(mp(a,b));
    }
    int md; scanf("%d",&md);
    set<PII> target_edges;
    FOR(i,1,md){
        int a,b; scanf("%d%d", &a, &b);
        if (a > b){
            swap(a,b);
        }
        // printf("Final edge %d %d\n", a, b);
        final_edges[a].push_back(b);
        final_edges[b].push_back(a);
        target_edges.insert(mp(a,b));
    }
    vis[1] = 1;
    dfs(1, true);
    set<int> one_initial_edges;
    for(auto b: initial_edges[1]){
        one_initial_edges.insert(b);
    }
    for (auto v: dfs_order){
        // printf("DFS order: %d\n", v);
        if (v != 1 && one_initial_edges.find(v) == one_initial_edges.end()){
            moves.emplace_back('+', mp(1, v));
            existing_edges.insert(mp(1,v));
        }
    }

    for (auto edge : existing_edges){
        int a = edge.e1, b = edge.e2;
        if (a == 1){
            continue; // we'll deal with it later
        }
        if (target_edges.find(edge) == target_edges.end()){
            moves.emplace_back('-', mp(a, b));
        }
    }

    FOR(i,1,n){
        vis[i] = 0;
    }
    dfs_order.clear();

    vis[1] = 1;
    dfs(1, false);
    reverse(ALL(dfs_order));

    for(auto &v: dfs_order){
        // printf("Reversed final DFS order %d\n", v);
        if (v != 1 && target_edges.find(mp(1,v)) == target_edges.end()){
            moves.emplace_back('-', mp(1, v));
        }
    }
    printf("%d\n", moves.size());
    for(auto &move: moves){
        char t = move.e1;
        int a = move.e2.e1, b = move.e2.e2;
        printf("%c %d %d\n", t, a, b);
    }
}


//1. take any node (atom) eg. 1
//2. connect node 1 to all other nodes (decide on order
//   using dfs from that node) [30,000 moves]
//3. transform the remainder of the graph using 1 
//   as connector [100,000 moves]
//4. unwind the connections of node 1 (use DFS 
//   on the *new* target graph to set order) [30,000 moves]