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

using namespace std;

int n, m_have, m_want;
int everyone_node = 2;
vector<unordered_set<int>> have, want;
vector<pair<int,int>> have_input_edges;
//unordered_set<pair<int,int>> have_edges;
//unordered_set<pair<int,int>> want_edges;

bool V1[30100], V2[30100];

struct Move {
	enum MoveType {
		ADD,
		REMOVE
	};
	int a, b;
	MoveType move_type;

	Move(int a, int b, MoveType move_type): a(a), b(b), move_type(move_type) {};
};

vector<Move> results;

void dfs_add_nodes(int a, int prev) {
	V1[a] = true;
	for (auto idx = have[a].begin(); idx != have[a].end(); idx++) {
		if (V1[*idx]) continue;
		if (!have[everyone_node].contains(*idx)) {
			results.push_back(Move(everyone_node, *idx, Move::ADD));
			have[everyone_node].insert(*idx);
			have[*idx].insert(everyone_node);
		}
		dfs_add_nodes(*idx, a);
	}
}

void add_missing_edges(int a) {
	for (auto idx = want[a].begin(); idx != want[a].end(); idx++) {
		if (!have[a].contains(*idx)) {
			results.push_back(Move(a, *idx, Move::ADD));
			have[a].insert(*idx);
			have[*idx].insert(a);
		}
	}
}

void remove_unnecessary_edges() {
	for (auto edge = have_input_edges.begin(); edge != have_input_edges.end(); edge++) {
		if (edge->first == everyone_node || edge->second == everyone_node) continue;
		if (!want[edge->first].contains(edge->second)) {
			results.push_back(Move(edge->first, edge->second, Move::REMOVE));
			have[edge->first].erase(edge->second);
			have[edge->second].erase(edge->first);
		}
	}
}

void dfs_remove_nodes(int a) {
	V2[a] = true;
	for (auto idx = want[a].begin(); idx != want[a].end(); idx++) {
		if (V2[*idx]) continue;
		dfs_remove_nodes(*idx);
	}
	if (!want[everyone_node].contains(a)) {
		results.push_back(Move(everyone_node, a, Move::REMOVE));
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n + 1; i++) {
		have.push_back(unordered_set<int>({i}));
		want.push_back(unordered_set<int>({i}));
	}
	int a, b;
	scanf("%d", &m_have);
	for (int i = 0; i < m_have; i++) {
		scanf("%d%d", &a, &b);
		have[a].insert(b);
		have[b].insert(a);
		have_input_edges.push_back(make_pair(a,b));
	}
	scanf("%d", &m_want);
	for (int i = 0; i < m_want; i++) {
		scanf("%d%d", &a, &b);
		want[a].insert(b);
		want[b].insert(a);
	}
	if (n == 2) {
		printf("0\n");
		return 0;
	}

	dfs_add_nodes(everyone_node, 0);
	for (int i = 1; i <= n; i++) add_missing_edges(i);
	remove_unnecessary_edges();
	dfs_remove_nodes(everyone_node);
	
	// Print results;
	printf("%d\n", results.size());
	for (auto idx = results.begin(); idx != results.end(); idx++) {
		if (idx->move_type == Move::ADD) {
			printf("+ %d %d\n", idx->a, idx->b);
		} else if (idx->move_type == Move::REMOVE) {
			printf("- %d %d\n", idx->a, idx->b);
		}
	}
}