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
135
136
137
138
139
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <string>
#include <unordered_set>

using namespace std;

vector<vector<int>> given;
vector<unordered_set<int>> given_set;
vector<vector<int>> desired;
vector<unordered_set<int>> desired_set;

vector<string> operations;

void add_edge(int a, int b) {
	if (given_set[a].find(b) != given_set[a].end()) {
		return;
	}
	given[a].push_back(b);
	given_set[a].insert(b);
	given[b].push_back(a);
	given_set[b].insert(a);
	operations.push_back("+ " + to_string(a + 1) + " " + to_string(b + 1));
}

void remove_edge(int a, int b) {
	if (given_set[a].find(b) == given_set[a].end()) {
		return;
	}
	given_set[a].erase(b);
	given_set[b].erase(a);
	operations.push_back("- " + to_string(a + 1) + " " + to_string(b + 1));
}

void add_additional_edges(int a) {
	for (auto u : desired[a]) {
		if (given_set[a].find(u) == given_set[a].end()) {
			add_edge(a, u);
		}
	}
}

void remove_edges(int a) {
	for (auto u : given[a]) {
		if (u != 0 && desired_set[a].find(u) == desired_set[a].end()) {
			remove_edge(a, u);
		}
	}
	if(desired_set[a].find(0) == desired_set[a].end())
		remove_edge(a, 0);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	given.resize(n);
	desired.resize(n);
	given_set.resize(n);
	desired_set.resize(n);
	int m;
	cin >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		given[a - 1].push_back(b - 1);
		given_set[a - 1].insert(b - 1);
		given[b - 1].push_back(a - 1);
		given_set[b - 1].insert(a - 1);
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		desired[a - 1].push_back(b - 1);
		desired_set[a - 1].insert(b - 1);
		desired[b - 1].push_back(a - 1);
		desired_set[b - 1].insert(a - 1);
	}

	queue<int> s;
	vector<bool> visited(given.size(), false);
	visited[0] = true;
	for (auto i : given[0]) {
		s.push(i);
		visited[i] = true;
	}

	vector<int> leafs;

	while (!s.empty()) {
		int current = s.front();
		s.pop();
		visited[current] = true;
		add_edge(0, current);
		int count_nodes = 0;
		for (int i = 0; i < given[current].size(); i++) {
			if (!visited[given[current][i]]) {
				s.push(given[current][i]);
				count_nodes++;
			}
		}
		if (count_nodes == 0) {
			leafs.push_back(current);
		}
	}

	for (int i = 1; i < n; i++) {
		add_additional_edges(i);
	}

	vector<bool> visited2(given.size(), false);
	for (auto i : leafs) {
		s.push(i);
		visited2[i] = true;
	}
	while (!s.empty()) {
		int current = s.front();
		s.pop();
		visited2[current] = true;
		remove_edges(current);
		for (int i = 0; i < given[current].size(); i++) {
			if (given[current][i] && !visited2[given[current][i]]) {
				s.push(given[current][i]);
			}
		}
	}

	cout << operations.size() << endl;
	for (auto i : operations) {
		cout << i << endl;
	}
}