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
#include <iostream>
#include <ranges>
#include <vector>
#include <queue>

using namespace std;

vector<tuple<bool, int, int>> toStar(int n, vector<vector<int>>& kraw) {
	int center = 1;
	vector<bool> conn(n, false);
	queue<int> q({center});
	conn[center] = true;
	vector<tuple<bool, int, int>>res;
	int v;
	while(!q.empty()) {
		v = q.front();
		q.pop();
		for(auto u: kraw[v]) {
			if (!conn[u]) {
				if (v != center) res.push_back({true, center, u});
				conn[u] = true;
				q.push(u);
			}
		}
	}
	for(int v = 1; v <= n; v++) {
		for(auto u: kraw[v]) {
			if (v < u && v != center && u != center) {
				res.push_back({false, v, u});
			}
		}
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;	
	cin >> n;
	vector<vector<int>> kraw(n + 1);
	int m;
	cin >> m;
	for(auto& v: kraw) {
		v.clear();
	}
	int a, b;
	for(int i = 0; i < m; i++) {
		cin >> a >> b;	
		kraw[a].push_back(b);
		kraw[b].push_back(a);
	}
	auto fi = toStar(n, kraw);
	cin >> m;
	for(auto& v: kraw) {
		v.clear();
	}
	for(int i = 0; i < m; i++) {
		cin >> a >> b;	
		kraw[a].push_back(b);
		kraw[b].push_back(a);
	}
	auto se = toStar(n, kraw);
	cout << fi.size() + se.size() << "\n";	
	for(auto [is, x, y]: fi) {
		if (is) cout << "+ ";
		else cout << "- ";
		cout << x << " " << y << "\n";
	}
	for(auto [is, x, y]: ranges::reverse_view(se)) {
		if (is) cout << "- ";
		else cout << "+ ";
		cout << x << " " << y << "\n";
	}
}