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
#include <bits/stdc++.h>
using std::cin, std::cout, std::vector;

void init_io() {
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}

struct Move {
  bool add;
  unsigned a;
  unsigned b;

  Move inverted() const {
    return Move{!add, a, b};
  }

  void print() const {
    cout << (add ? '+' : '-') << ' ' << (a + 1) << ' ' << (b + 1) << "\n";
  }
};

constexpr unsigned depth_none = -1u;

struct Node {
  unsigned depth = depth_none;
  vector<unsigned> edges;
};

class Graph {
public:
  void read(const unsigned num_nodes) {
    unsigned num_edges;
    cin >> num_edges;
    nodes.resize(num_nodes);
    queue.reserve(num_nodes + num_edges);
    for (unsigned i=0; i<num_edges; ++i) {
      unsigned a, b;
      cin >> a >> b;
      --a; --b;
      nodes[a].edges.push_back(b);
      nodes[b].edges.push_back(a);
    }
  }

  vector<Move> convert_to_star() {
    vector<Move> moves;

    // BFS: add edges to 0
    nodes[0].depth = 0;
    queue.push_back(0);

    for (unsigned queue_index = 0; queue_index < queue.size(); ++queue_index) {
      const unsigned a = queue[queue_index];
      if (nodes[a].depth >= 2) {
        moves.push_back(Move{true, 0, a});
      }
      for (const unsigned b: nodes[a].edges) {
        if (nodes[b].depth == depth_none) {
          nodes[b].depth = nodes[a].depth + 1;
          queue.push_back(b);
        }
      }
    }

    // Remove other edges
    for (unsigned a = 1; a < nodes.size(); ++a) {
      for (const unsigned b: nodes[a].edges) {
        if (a < b) {
          moves.push_back(Move{false, a, b});
        }
      }
    }

    return moves;
  }

private:
  vector<Node> nodes;
  vector<unsigned> queue;
};

int main() {
  init_io();

  unsigned n;
  cin >> n;

  Graph graph_a;
  graph_a.read(n);
  vector<Move> moves_a = graph_a.convert_to_star();

  Graph graph_b;
  graph_b.read(n);
  vector<Move> moves_b = graph_b.convert_to_star();

  cout << (moves_a.size() + moves_b.size()) << "\n";
  for (const Move move : moves_a) move.print();
  for (auto it = moves_b.rbegin(); it != moves_b.rend(); ++it) {
    it->inverted().print();
  }
}