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
#include <cstdio>
#include <vector>
#include <set>
#include <queue>

using namespace std;

int main () {
	int n;
	scanf("%d", &n);
	int ms;
	scanf("%d", &ms);
	vector<vector<int> > source(n, vector<int>());
	set<pair<int, int> > source_edges;
	vector<pair<bool, pair<int, int> > > result;
	for (int i = 0; i < ms; ++i) {
		int a, b;
		scanf("%d %d", &a, &b);
		if (a > b) {
			int tmp = a;
			a = b;
			b = tmp;
		}
		--a;
		--b;
		source[a].push_back(b);
		source[b].push_back(a);
		source_edges.insert(make_pair(a, b));
	}
	vector<int> source_bfs_order;
	source_bfs_order.reserve(n + 8);
	vector<bool> source_visited(n, false);
	queue<int> q;
	q.push(0);
	while (!q.empty()) {
		int node = q.front();
		q.pop();
		if (source_visited[node]) {
			continue;
		}
		source_visited[node] = true;
		source_bfs_order.push_back(node);
		for (vector<int>::iterator it = source[node].begin(); it != source[node].end(); it++) {
			if (source_visited[*it]) {
				continue;
			}
			q.push(*it);
		}
	}
	for (vector<int>::iterator it = source_bfs_order.begin(); it != source_bfs_order.end(); it++) {
		if (*it == 0) {
			continue;
		}
		if (source_edges.find(make_pair(0, *it)) != source_edges.end()) {
			continue;
		}
		result.push_back(make_pair(true, make_pair(1, *it + 1)));
	}
	int md;
	scanf("%d", &md);
	vector<vector<int> > destination(n, vector<int>());
	set<pair<int, int> > destination_edges;
	for (int i = 0; i < md; ++i) {
		int a, b;
		scanf("%d %d", &a, &b);
		if (a > b) {
			int tmp = a;
			a = b;
			b = tmp;
		}
		--a;
		--b;
		destination[a].push_back(b);
		destination[b].push_back(a);
		destination_edges.insert(make_pair(a, b));
	}
	vector<int> destination_bfs_order;
	destination_bfs_order.reserve(n + 8);
	vector<bool> destination_visited(n, false);
	queue<int> q2;
	q2.push(0);
	while (!q2.empty()) {
		int node = q2.front();
		q2.pop();
		if (destination_visited[node]) {
			continue;
		}
		destination_visited[node] = true;
		destination_bfs_order.push_back(node);
		for (vector<int>::iterator it = destination[node].begin(); it != destination[node].end(); it++) {
			if (destination_visited[*it]) {
				continue;
			}
			q2.push(*it);
		}
	}
	for (set<pair<int, int> >::iterator it = source_edges.begin(); it != source_edges.end(); it++) {
		if (it->first == 0) {
			continue;
		}
		if (destination_edges.find(*it) == destination_edges.end()) {
			result.push_back(make_pair(false, make_pair(it->first + 1, it->second + 1)));
		}
	}
	for (set<pair<int, int> >::iterator it = destination_edges.begin(); it != destination_edges.end(); it++) {
		if (it->first == 0) {
			continue;
		}
		if (source_edges.find(*it) == source_edges.end()) {
			result.push_back(make_pair(true, make_pair(it->first + 1, it->second + 1)));
		}
	}
	for (vector<int>::reverse_iterator it = destination_bfs_order.rbegin(); it != destination_bfs_order.rend(); it++) {
		if (*it == 0) {
			continue;
		}
		if (destination_edges.find(make_pair(0, *it)) != destination_edges.end()) {
			continue;
		}
		result.push_back(make_pair(false, make_pair(1, *it + 1)));
	}
	printf("%d\n", result.size());
	for (vector<pair<bool, pair<int, int> > >::iterator it = result.begin(); it != result.end(); it++) {
		printf("%c %d %d\n", it->first ? '+' : '-', it->second.first, it->second.second);
	}
	return 0;
}