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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

vector<int> v1[30009];
vector<int> v2[30009];
set<pair<int, int> > s1;
set<pair<int, int> > s2;

vector<pair<int, int> > history;
vector<pair<int, int> > history_minus;

bool odw[30009];
int d[30009];

void fill_vertex(int st) {
	queue<int> q;
	q.push(st);
	odw[st] = true;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int c : v1[x]) {
			if (odw[c]) {
				continue;
			}
			odw[c] = true;
			q.push(c);
			int a = st;
			int b = c;
			if (a > b) swap(a, b);
			if (s1.find({a, b}) == s1.end()) {
				v1[a].push_back(b);
				v1[b].push_back(a);
				history.push_back({a, b});
				s1.insert({a, b});
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	int m1, m2;
	cin >> m1;
	for (int i = 0; i < m1; i++) {
		int a, b;
		cin >> a >> b;
		v1[a].push_back(b);
		v1[b].push_back(a);
		if (a > b) swap(a, b);
		s1.insert({a, b});
	}
	cin >> m2;
	for (int i = 0; i < m2; i++) {
		int a, b;
		cin >> a >> b;
		v2[a].push_back(b);
		v2[b].push_back(a);
		if (a > b) swap(a, b);
		s2.insert({a, b});
	}
	if (n == 2) {
		cout << "0\n";
		return 0;
	}
	int st = 1;
	for (int i = 1; i <= n; i++) {
		if (v2[i].size() > 1) {
			st = i;
			break;
		}
	}
	fill_vertex(st);

	for (auto c : s2) {
		if (s1.find(c) == s1.end()) {
			history.push_back(c);
			v1[c.first].push_back(c.second);
			v1[c.second].push_back(c.first);
			s1.insert(c);
		}
	}

	for (int i = 1; i <= n; i++) {
		for (auto c : v1[i]) {
			int a = i;
			int b = c;
			if (a > b) swap(a, b);
			if (s2.find({a, b}) != s2.end()) {
				d[i]++;
			}
		}
	}

	set<int> to_remove;
	for (auto c : s1) {
		if (s2.find(c) == s2.end()) {
			if (c.first != st && c.second != st) {
				history_minus.push_back(c);
			} else {
				auto [a, b] = c;
				if (a == st) swap(a, b);
				to_remove.insert(a);
			}
		}
	}
	queue<int> qu;
	vector<int> quu;
	for (int c : to_remove) {
		if (d[c] == 1) {
			qu.push(c);
			quu.push_back(c);
		}
	}
	for (int c : quu) {
		history_minus.push_back({st, c});
		to_remove.erase(c);
	}
	while (!to_remove.empty()) {
		if (qu.empty()) {
			int x = *(to_remove.begin());
			to_remove.erase(x);
			history_minus.push_back({st, x});
			qu.push(x);
		}
		int x = qu.front();
		qu.pop();
		for (int c : v1[x]) {
			int a = x;
			int b = c;
			if (a > b) swap(a, b);
			if (s2.find({a, b}) != s2.end()) {
				d[c]--;
				if (d[c] == 1 && to_remove.find(c) != to_remove.end()) {
					qu.push(c);
					history_minus.push_back({st, c});
					to_remove.erase(c);
				}
			}
		}
	}

	cout << history.size() + history_minus.size() << "\n";
	for (auto h : history) {
		cout << "+ " << h.first << " " << h.second << "\n";
	}
	for (auto h : history_minus) {
		cout << "- " << h.first << " " << h.second << "\n";
	}
	return 0;
}