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
#include <algorithm>
#include <iostream>
#include <vector>
#include <utility>
#include <set>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, ms, md;
	vector<pair<char,pair<int,int>>> out;

	cin >> n;
	vector<set<int>> ori(n+1);
	vector<set<int>> dest(n+1);
	vector<set<int>> mid(n+1);
	cin >> ms;
	int a_in, b_in;
	for(int i = 0; i < ms; i++) {
		cin >> a_in >> b_in;
		if(a_in > b_in) {
			swap(a_in,b_in);
		}
		ori[a_in].insert(b_in);
		mid[a_in].insert(b_in);
		mid[b_in].insert(a_in);
	}
	cin >> md;
	for(int i = 0; i < md; i++) {
		cin >> a_in >> b_in;
		if(a_in > b_in) {
			swap(a_in,b_in);
		}
		dest[a_in].insert(b_in);
	}
	for(int a = 1; a <=n; a++) {
		vector<int> to_add;
		set_difference(dest[a].begin(),dest[a].end(),ori[a].begin(),ori[a].end(),back_inserter(to_add));
		for(auto& b: to_add) {
			vector<int> inter;
			set_intersection(mid[a].begin(),mid[a].end(),mid[b].begin(),mid[b].end(),back_inserter(inter));
			if((int)inter.size() == 0) {
				int new_e = *mid[a].begin();
				mid[b].insert(new_e);
				mid[new_e].insert(b);

				out.push_back({'+',{new_e,b}});
				if(new_e > b) {
					swap(new_e,b);
				}
				ori[new_e].insert(b);
			}
			mid[b].insert(a);
			mid[a].insert(b);

			out.push_back({'+',{a,b}});
			if(a > b) {
				swap(a,b);
			}
			ori[a].insert(b);
		}
	}
	// usuwanie
	vector<set<int>> erased(n+1);
	bool work = true;
	while(work) {
		work = false;
		for(int a = 1; a <=n; a++) {
		
			vector<int> to_del;
			set_difference(ori[a].begin(),ori[a].end(),dest[a].begin(),dest[a].end(),back_inserter(to_del));
			for(auto& b: to_del) {
				vector<int> inter;
				set_intersection(mid[a].begin(),mid[a].end(),mid[b].begin(),mid[b].end(),back_inserter(inter));
				if((int)inter.size() == 0) {
					int new_e1 = -1;
					int new_e2 = -1;
					for(const auto& e:mid[a]) {
						if(erased[e].contains(b) == false && e != b) {
							new_e1 = e;
							new_e2 = b;
							break;
						}
					}
					if(new_e1 == -1) {
						for(const auto& e:mid[b]) {
							if(erased[e].contains(a) == false && e != a) {
								new_e1 = e;
								new_e2 = a;
								break;
							}
						}
					}
					mid[new_e2].insert(new_e1);
					mid[new_e1].insert(new_e2);
					out.push_back({'+',{new_e1,new_e2}});
					work = true;
					if(new_e1 > new_e2) {
						swap(new_e1,new_e2);
					}
					ori[new_e1].insert(new_e2);
				}
				out.push_back({'-',{a,b}});
				erased[a].insert(b);
				erased[b].insert(a);
				mid[a].erase(b);
				mid[b].erase(a);
				if(a > b) {
					swap(a,b);
				}
				ori[a].erase(b);
			}
		}
	}
	cout<<(int)out.size()<< "\n";
	for(const auto& i: out) {
		cout<<i.first<<" "<<i.second.first<<" "<<i.second.second<<"\n";
	}
	return 0;
}