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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <queue>
#include <ranges>

using namespace std;

vector<int> bfs(int a, int b, const vector<vector<int>>& graph)
{
  queue<int> q;
  vector<int> parent(graph.size(), -1);
  parent[a] = a;
  q.push(a);
  while(!q.empty())
  {
    int k = q.front();
    q.pop();
    if(k == b)
    {
      break;
    }
    for(auto x : graph[k])
    {
      if(parent[x] == -1)
      {
        parent[x] = k;
        q.push(x);
      }
    }

  }

  vector<int> rev_path;
  int cur = b;
  while(cur != a)
  {
    rev_path.push_back(cur);
    cur = parent[cur];
  }
  rev_path.push_back(a);
  return vector<int>(rev_path.rbegin(), rev_path.rend());
}

struct edge
{
  bool to_add;
  int x,y;
};

void add_edge(int a, int b, vector<vector<int>>& graph, vector<vector<bool>>& matrix, vector<edge>& edges)
{
  matrix[a][b] = matrix[b][a] = true;
  graph[a].push_back(b);
  graph[b].push_back(a);

  edges.push_back(edge{
    .to_add = true,
    .x = a,
    .y = b,   
  });
}

int main()
{
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<vector<int>> graph(n+1);
  vector<vector<bool>> matrix(n+1, vector<bool>(n+1, 0));
  vector<vector<bool>> expected_matrix(n+1, vector<bool>(n+1, 0));

  
  int m1;
  cin >> m1;
  for(int i = 0; i < m1; i++)
  {
    int a,b;
    cin >> a >> b;
    matrix[a][b] = matrix[b][a] = true;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }

  vector<edge> edges;

  int m2;
  cin >> m2;
  for(int i = 0; i < m2; i++)
  {
    int a,b;
    cin >> a >> b;
    expected_matrix[a][b] = expected_matrix[b][a] = true;
    if (matrix[a][b] != true && matrix[b][a] != true) 
    {
      vector<int> path = bfs(a, b, graph);
      for(int j = 2; j < path.size() - 1; j++)
      {
        add_edge(a, path[j], graph, matrix, edges);
      }
      add_edge(a, b, graph, matrix, edges);
    }
  }

  for(int i = 1; i <= n; i++)
  {
    for(int j = 1; j < i; j++)
    {
      if(matrix[i][j] != expected_matrix[i][j])
      {
        edges.push_back(edge{
          .to_add = false,
          .x = i,
          .y = j,   
        });
      }
    }
  }

  cout << edges.size() << endl;
  for(auto e : edges)
  {
    if(e.to_add)
    {
      cout << "+ ";
    }
    else 
    {
      cout << "- ";
    }
    cout << e.x << " " << e.y <<endl;
  }
}