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
#include<bits/stdc++.h>
using namespace std;
int n, m1, m2;
constexpr int MAXN = 3e4+2;
vector<int> adj[MAXN];
bitset<MAXN> git[MAXN],  git1[MAXN];
bitset<MAXN> vis;

void dfs1(int v, string &odp, int &r) {
  vis[v] = 1;
  if(!git[1][v] && v != 1) {
    git[1][v] = git[v][1] = 1;
    odp += "+ 1 " + to_string(v) + "\n";
    r++;
  }
  for(int s : adj[v]) {
    if(!vis[s]) dfs1(s, odp, r);
  }
}

void dfsD(int v, int p, string &odp, int &r) {
  //cerr << "ODWIEDZIELM: " << v << " PRZEZ: " << p << '\n';
  if(!vis[v]) {
    vis[v] = 1;
    for(int s : adj[v]) {
      if(s != p) dfsD(s, v, odp, r);
    }
  }
  if(p != -1 && !git1[v][p]) {
    r++;
    odp += "- " + to_string(v) + " " + to_string(p) + "\n";
    git1[v][p] = git1[p][v] = 1;
  }
}

void dfsD1(int v, string &odp, int &r) {
  vis[v] = 1;
  for(int s : adj[v]) {
    if(!vis[s]) dfsD1(s, odp, r);
  }
  if(git[1][v] && !git1[1][v] && v != 1) {
    git[1][v] = git[v][1] = 0;
    odp += "- 1 " + to_string(v) + "\n";
    r++;
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  cin >> m1;
  for(int i = 0; i < m1; ++i) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
    git[a][b] = git[b][a] = 1;
  }
  string odp = "";
  int r = 0;
  dfs1(1, odp, r);
  cin >> m2;
  for(int i = 0; i < m2; ++i) {
    int a, b;
    cin >> a >> b;
    git1[a][b] = git1[b][a] = 1;
    if(!git[a][b]) {
      odp += "+ " + to_string(a) + " " + to_string(b) + "\n";
      git[a][b] = git[b][a] = 1;
      r++;
    }
  }
  vis.reset();
  dfsD(1, -1, odp, r);
  vis.reset();
  dfsD1(1, odp, r);
  cout << r << '\n' << odp;
}