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
// ALC: Alchemik Bajtazar [B] | 2024-03-12 | Solution by dkgl
// https://sio2.mimuw.edu.pl/c/pa-2024-1/p/alc/

#include <bits/stdc++.h>

using namespace std;

struct Node {
  vector<int> neighbours;
  bool visited = false;
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  vector<Node> nodes(n);
  set<pair<int, int>> remaining_edges;

  auto add_edge = [&](int a, int b) {
    if (a > b) swap(a, b);
    nodes[a].neighbours.push_back(b);
    nodes[b].neighbours.push_back(a);
    remaining_edges.insert({ a, b });
  };

  int m_start;
  cin >> m_start;
  while (m_start--) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    add_edge(a, b);
  }
  queue<int> queue;
  auto &root = nodes[0];
  root.visited = true;
  for (auto u: root.neighbours) {
    nodes[u].visited = true;
    queue.push(u);
  }
  vector<pair<int, int>> added_edges;
  while (!queue.empty()) {
    auto v = queue.front();
    queue.pop();
    for (auto u: nodes[v].neighbours) {
      if (nodes[u].visited) continue;
      nodes[u].visited = true;
      queue.push(u);
      add_edge(0, u);
      added_edges.push_back({ 0, u });
    }
  }

  int m_final;
  cin >> m_final;
  while (m_final--) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    if (a > b) swap(a, b);
    auto el = remaining_edges.find({ a, b });
    if (el == remaining_edges.end()) added_edges.push_back({ a, b });
    else remaining_edges.erase(el);
  }
  cout << added_edges.size() + remaining_edges.size() << '\n';
  for (auto &[a, b]: added_edges) cout << "+ " << a + 1 << ' ' << b + 1 << '\n';
  for (auto &[a, b]: remaining_edges) cout << "- " << a + 1 << ' ' << b + 1 << '\n';

  cout.flush();
  return 0;
}