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
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;

const int N = 30000 + 9;
int nextInt() { int n; scanf("%d", &n); return n; }

int n;
vector<int> g1[N];
vector<int> g2[N];
vector<pair<int, int>> add1;
vector<pair<int, int>> add2;
set<pair<int, int>> s1;
set<pair<int, int>> s2;

int visited[N];
int step;

void bfs(vector<int> g[], vector<pair<int, int>>& add) {
	++step;
	queue<int> q;
	q.push(1);
	visited[1] = step;
	for (int d = 0; !q.empty(); ++d) {
		int todo = q.size();
		for (int ___ = 0; ___ < todo; ++___) {
			int v = q.front();
			q.pop();
			if (d >= 2)
				add.push_back({ 1, v });
			for (int i = 0; i < g[v].size(); ++i) {
				int vv = g[v][i];
				if (visited[vv] == step)
					continue;
				q.push(vv);
				visited[vv] = step;
			}
		}
	}
}

void fillMissing(vector<int> g[], const set<pair<int, int>>& s, vector<pair<int, int>>& add) {
	for (int i = 1; i <= n; ++i)
		for (int j = 0; j < g[i].size(); ++j)
			if (i < g[i][j])
				if (s.count({ i, g[i][j] }) == 0)
					add.push_back({ i, g[i][j] });
}

int myMin(int a, int b) { return a <= b ? a : b; }
int myMax(int a, int b) { return a >= b ? a : b; }

void readGraph(vector<int> g[], set<pair<int, int>> &s) {
	int m = nextInt();
	for (int i = 0; i < m; ++i) {
		int a = nextInt();
		int b = nextInt();
		g[a].push_back(b);
		g[b].push_back(a);
		s.insert({ myMin(a, b), myMax(a, b) });
	}
}

int main() {
	n = nextInt();
	for (int i = 2; i <= n; ++i) {
		s1.insert({ 1, i });
		s2.insert({ 1, i });
	}
	readGraph(g1, s1);
	readGraph(g2, s2);

	bfs(g1, add1);
	fillMissing(g2, s1, add1);

	bfs(g2, add2);
	fillMissing(g1, s2, add2);

	printf("%d\n", add1.size() + add2.size());
	for (int i = 0; i < add1.size(); ++i)
		printf("+ %d %d\n", add1[i].first, add1[i].second);
	for (int i = add2.size() - 1; i >= 0; --i)
		printf("- %d %d\n", add2[i].first, add2[i].second);

	return 0;
}