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
#include <vector>
#include <string>
#include <unordered_set>
#include <algorithm>
#include <iostream>

class Solution {
public:
	Solution(int aAtomsCount)
		: atomsCount{aAtomsCount}
		, originalGraphAdj(atomsCount + 1, std::unordered_set<int>())
	{}

	void run() {
		initializeOriginalGraph();
		initializeDesiredGraph();
		createBindingsToAdd();
		createBindingsToRemove();
		prepareBindingsToRemove();
		printBindings();
	}
	
	void initializeOriginalGraph() {
		int originalBindingsCount;
		std::cin >> originalBindingsCount;
		
		for (int i = 0; i < originalBindingsCount; i++) {
			int a, b;
			std::cin >> a >> b;
			if (a > b) {
				std::swap(a, b);
			}
			originalGraph.push_back({a, b});
			originalGraphAdj[a].insert(b);
			originalGraphAdj[b].insert(a);
			originalBindingsSet.insert(std::to_string(a) + "." + std::to_string(b));
		}
		
	}
	
	void initializeDesiredGraph() {
		int desiredBindingsCount;
		std::cin >> desiredBindingsCount;
		for (int i = 0; i < desiredBindingsCount; i++) {
			int a, b;
			std::cin >> a >> b;
			if (a > b) {
				std::swap(a, b);
			}
			desiredGraph.push_back({a,b});
			desiredBindingsSet.insert(std::to_string(a) + "." + std::to_string(b));
		}
	}
	
	void createBindingsToAdd() {
		std::unordered_set<std::string> addedHelperBindings;
		for (auto& entry : desiredGraph) {
			std::string tmp = std::to_string(entry.first) + "." + std::to_string(entry.second);
			if (originalBindingsSet.find(tmp) == originalBindingsSet.end()) {
				int helperA = *originalGraphAdj[entry.first].begin();
				int helperB = entry.second;
				if (helperA > helperB) {
					std::swap(helperA, helperB);
				}
				std::string tmpHelper = std::to_string(helperA) + "." + std::to_string(helperB);
				if (originalBindingsSet.find(tmpHelper) == originalBindingsSet.end()
					&& addedHelperBindings.find(tmpHelper) == addedHelperBindings.end()) {
					addedHelperBindings.insert(tmpHelper);
					toAdd.push_back({helperA, helperB});
					toRemove.push_back({helperA, helperB});
				}
				if (addedHelperBindings.find(tmp) == addedHelperBindings.end()) {
					toAdd.push_back(entry);
					addedHelperBindings.insert(tmp);
				} else {
					auto it = std::find(toRemove.begin(), toRemove.end(), entry);
					toRemove.erase(it);
				}
			}
		}
	}
	
	void createBindingsToRemove() {
		for (auto& entry : originalGraph) {
			std::string tmp = std::to_string(entry.first) + "." + std::to_string(entry.second);
			if (desiredBindingsSet.find(tmp) == desiredBindingsSet.end()) {
				toRemove.push_back(entry);
			}
		}
	}
	
	void prepareBindingsToRemove() {
		std::sort(toRemove.begin(), toRemove.end(), [](auto& entry1, auto& entry2) {
			return entry1.first < entry2.first || (entry1.first == entry2.first && entry1.second < entry2.second);
		});
	}
	
	void printBindings() {
		std::cout << toAdd.size() + toRemove.size() << "\n";
		for (auto& entry : toAdd) {
			std::cout << "+ " << entry.first << " " << entry.second << "\n";
		}
		for (auto& entry : toRemove) {
			std::cout << "- " << entry.first << " " << entry.second << "\n";
		}
	}
	
	int atomsCount;
	std::vector<std::pair<int,int>> originalGraph;
	std::vector<std::unordered_set<int>> originalGraphAdj;
	std::vector<std::pair<int,int>> desiredGraph;
	std::vector<std::pair<int,int>> toAdd;
	std::vector<std::pair<int,int>> toRemove;
	std::unordered_set<std::string> originalBindingsSet;
	std::unordered_set<std::string> desiredBindingsSet;
};

int main() {
	int atomsCount;
	std::cin >> atomsCount;
	
	Solution solution(atomsCount);
	solution.run();
	
	return 0;
}