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
#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;
const int SIZE = 3e4 + 5;
int n, MSUM = 0;

void decode(vector<int> v, bool rev){
	if (v[0] ^ rev == 1)	cout << "+ ";
	else					cout << "- ";
	cout << v[1] << ' ' << v[2] << '\n';
}

class graph {
	bool B[SIZE] = {};
	unordered_set <int> S[SIZE];
	vector <vector<int>> OP;
	void dodaj(int a, int b) {
		if (S[a].count(b) || a == b) return;
		S[a].insert(b);
		S[b].insert(a);
		OP.push_back({ 1, a, b });
		MSUM++;
	}
	void usun(int a, int b) {
		if (!S[a].count(b) || a == b) return;
		S[a].erase(b);
		S[b].erase(a);
		OP.push_back({ 0, a, b });
		MSUM++;
	}
public:
	void debug()
	{
		for (int i = 1; i <= n; i++)
		{
			cout << i << '\t';
			for (auto j : S[i]) cout << j << ' ';
			cout << '\n';
		}
		cout << OP.size() << '\n';
		for (auto i : OP) decode(i, 0);
		cout << "\n------------------------------\n\n";
	}
	void input()
	{
		int m; cin >> m;
		while (m-- > 0) {
			int a, b;
			cin >> a >> b;
			S[a].insert(b);
			S[b].insert(a);
		}
	}
	void dfs(int u)
	{
		B[u] = true;
		dodaj(u, 1);
		for (auto v : S[u]) if (!B[v]) dfs(v);
	}
	void flower()
	{
		dfs(1);
		//debug();
		for (int i = 2; i <= n; i++)
		{
			vector<int> do_usuniecia = {};
			for (auto& j : S[i]) if (j != 1) do_usuniecia.push_back(j);
			for (auto j : do_usuniecia) usun(i, j);
		}
		//debug();
	}
	void output(bool rev){
		if (rev) reverse(OP.begin(), OP.end());
		for (auto i : OP) decode(i, rev);
	}
};
graph start, koniec;
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;

	if (n == 2) return cout << "0\n", 0;

	start.input(); start.flower(); 
	koniec.input(); koniec.flower();
	
	if (MSUM > (int)2e5) cout << "klapsa";
	cout << MSUM << '\n';
	start.output(0); koniec.output(1);
}