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

using namespace std;

int n, ms, md, i, a, b, op_id;
set<int> conn_s[30001];
set<int> conn_d[30001];
int visited[30001];
char op[200001];
int op_a[200001];
int op_b[200001];

void build_skeleton(int node) {
  if (visited[node] != 1) {
    visited[node] = 1;
    if (node != n) {
      if (conn_s[node].find(n) == conn_s[node].end()) {
        op[op_id] = '+';
        op_a[op_id] = n;
        op_b[op_id] = node;
        op_id++;
        conn_s[node].insert(n);
        conn_s[n].insert(node);
      }
    }
    for (set<int>::iterator it = conn_s[node].begin(); it != conn_s[node].end(); it++) {
      build_skeleton(*it);
    }
  }
}

void remove_unnecessary(int node) {
  if (visited[node] != 2) {
    visited[node] = 2;
    for (set<int>::iterator it = conn_d[node].begin(); it != conn_d[node].end(); it++) {
      remove_unnecessary(*it);
    }
    set<int>::iterator it = conn_s[node].begin();
    while (it != conn_s[node].end()) {
      // if needed to be deleted, connection with "n" will be deleted at the end, we need that behaviour (and we have it, set is sorted in ascending order)
      if (conn_d[node].find(*it) == conn_d[node].end()) {
        int x = *it;
        op[op_id] = '-';
        op_a[op_id] = node;
        op_b[op_id] = x;
        op_id++;
        it++;
        conn_s[node].erase(x);
        conn_s[x].erase(node);
      } else {
        it++;
      }
    }
  }
}

int main() {
  op_id = 0;

  scanf("%d", &n);

  for (i = 1; i <= n; i++) {
    visited[i] = 0;
  }

  scanf("%d", &ms);
  for (i = 0; i < ms; i++) {
    scanf("%d %d", &a, &b);
    conn_s[a].insert(b);
    conn_s[b].insert(a);
  }

  scanf("%d", &md);
  for (i = 0; i < md; i++) {
    scanf("%d %d", &a, &b);
    conn_d[a].insert(b);
    conn_d[b].insert(a);
  }

  // 1. connect all nodes with node "n"
  build_skeleton(n);

  // 2. build missing connections
  for (i = 1; i <= n; i++) {
    for (set<int>::iterator it = conn_d[i].begin(); it != conn_d[i].end(); it++) {
      if (conn_s[i].find(*it) == conn_s[i].end()) {
        op[op_id] = '+';
        op_a[op_id] = i;
        op_b[op_id] = *it;
        op_id++;
        conn_s[i].insert(*it);
        conn_s[*it].insert(i);
      }
    }
  }

  // 3. remove unnecessary connections (from the "end" of destination graph)
  remove_unnecessary(n);

  printf("%d\n", op_id);
  for (i = 0; i < op_id; i++) {
    printf("%c %d %d\n", op[i], op_a[i], op_b[i]);
  }

  return 0;
}