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

const int MAX_N = 3e4;
int n, m1, m2;

std::vector<int> list[MAX_N + 3];
std::vector<int> list2[MAX_N + 3];

std::set<std::pair<int, int>> s1, s2;

inline bool is_1(int x, int y) { return s1.count({x, y}) || s1.count({y, x}); }

inline bool is_2(int x, int y) { return s2.count({x, y}) || s2.count({y, x}); }

std::vector<std::pair<char, std::pair<int, int>>> R;

void add_edge(int x, int y) {
  R.push_back({'+', {x, y}});
  s1.insert({x, y});
}

void remove_edge(int x, int y) {
  R.push_back({'-', {x, y}});
  if (s1.count({x, y}))
    s1.erase({x, y});
  if (s1.count({y, x}))
    s1.erase({y, x});
}

std::vector<int> ord;
bool visited[MAX_N + 3];

void dfs(int v) {
  visited[v] = true;
  ord.push_back(v);
  for (auto u : list[v])
    if (!visited[u])
      dfs(u);
}

void dfs2(int v) {
  visited[v] = true;
  ord.push_back(v);
  for (auto u : list2[v])
    if (!visited[u])
      dfs2(u);
}

int main() {
  std::ios_base::sync_with_stdio(0);
  std::cin.tie(NULL);

  std::cin >> n;

  std::cin >> m1;
  for (int i = 1; i <= m1; i++) {
    int u, v;
    std::cin >> u >> v;
    list[u].push_back(v);
    list[v].push_back(u);
    s1.insert({u, v});
  }

  std::cin >> m2;
  for (int i = 1; i <= m2; i++) {
    int u, v;
    std::cin >> u >> v;
    list2[u].push_back(v);
    list2[v].push_back(u);
    s2.insert({u, v});
  }

  for (int i = 1; i <= n; i++)
    visited[i] = false;
  dfs(1);

  // Add 1 to everyone - <= 30 000 ops
  for (int i = 1; i < n; i++) {
    int u = ord[i];
    if (!is_1(1, u))
      add_edge(1, u);
  }

  // Remove unnecessary in G[V \ {1}] - <= 50 000 ops
  std::vector<std::pair<int, int>> to_remove;
  for (auto &[x, y] : s1) {
    if (x != 1 && y != 1 && !is_2(x, y))
      to_remove.push_back({x, y});
  }
  for (auto &[x, y] : to_remove)
    remove_edge(x, y);

  // Add missing in G[V \ {1}] - <= 50 000 ops
  for (auto &[x, y] : s2) {
    if (x != 1 && y != 1 && !is_1(x, y))
      add_edge(x, y);
  }

  ord.clear();
  for (int i = 1; i <= n; i++)
    visited[i] = false;
  dfs2(1);

  // Remove unecessary incident to 1 - <= 30 000 ops
  for (int i = ord.size() - 1; i >= 1; i--) {
    int u = ord[i];
    if (!is_2(1, u))
      remove_edge(1, u);
  }

  std::cout << R.size() << "\n";
  for (auto &[c, p] : R)
    std::cout << c << " " << p.first << " " << p.second << "\n";
}