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
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
#define pb push_back
const int INF = 2147483647;
const int N = 30005;

struct mov {
	bool add;
	int first, second;
	
	mov(bool a, int f, int s) {
		add = a;
		first = f;
		second = s;
	}
	
	void print() {
		if (add) printf("+ "); else printf("- ");
		printf("%d %d\n", first, second);
	}
};

int n, m, a, b, d1[N], d2[N], kol[N], i, w;
set<int> graf1[N], graf2[N];
queue<int> q;
vector<mov> result;

bool cmp1(int a, int b) {
	return d1[a] < d1[b];
}

bool cmp2(int a, int b) {
	return d2[a] < d2[b];
}

int main() {
scanf("%d %d", &n, &m);
while (m--) {
	scanf("%d %d", &a, &b);
	graf1[a].insert(b);
	graf1[b].insert(a);
}

scanf("%d", &m);
while (m--) {
	scanf("%d %d", &a, &b);
	graf2[a].insert(b);
	graf2[b].insert(a);
}

for (i=1;i<=n;i++) {
	d1[i] = d2[i] = -1;
	kol[i] = i;
}

while (q.size() > 0) q.pop();
d1[1] = 0;
q.push(1);
while (q.size() > 0) {
	w = q.front();
	q.pop();
	for (auto& w2 : graf1[w]) if (d1[w2] == -1) {
		d1[w2] = d1[w] + 1;
		q.push(w2);
	}
}

while (q.size() > 0) q.pop();
d2[1] = 0;
q.push(1);
while (q.size() > 0) {
	w = q.front();
	q.pop();
	for (auto& w2 : graf2[w]) if (d2[w2] == -1) {
		d2[w2] = d2[w] + 1;
		q.push(w2);
	}
}

sort(kol + 1, kol + n + 1, cmp1);

for (i=2;i<=n;i++) if (graf1[1].find(kol[i]) == graf1[1].end()) {
	mov mm(true, 1, kol[i]);
	result.pb(mm);
}

for (i=2;i<=n;i++) for (auto& w : graf2[i]) if (w > i && graf1[i].find(w) == graf1[i].end()) {
	mov mm(true, i, w);
	result.pb(mm);
}

for (i=2;i<=n;i++) for (auto& w : graf1[i]) if (w > i && graf2[i].find(w) == graf2[i].end()) {
	mov mm(false, i, w);
	result.pb(mm);
}

sort(kol + 1, kol + n + 1, cmp2);

for (i=n;i>=2;i--) if (graf2[1].find(kol[i]) == graf2[1].end()) {
	mov mm(false, 1, kol[i]);
	result.pb(mm);
}

printf("%d\n", result.size());
for (auto &w : result) w.print();

return 0;
}