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
// [2B] Alchemik Bajtazar, Kamil Debowski
#include <bits/stdc++.h>
using namespace std;

int n;

struct Graph {
	vector<vector<int>> edges;
	vector<bool> visited;
	vector<int> order;
	vector<bool> isOne; // has edge to 1
	vector<pair<int,int>> allEdges;

	void dfs(int a) {
		order.push_back(a);
		visited[a] = true;
		for (int b : edges[a]) {
			if (!visited[b]) {
				dfs(b);
			}
		}
	}
	Graph() {
		edges.resize(n+1);
		visited.resize(n+1);
		isOne.resize(n+1);
		int m;
		cin >> m;
		for (int i = 0; i < m; i++) {
			int a, b;
			cin >> a >> b;
			if (a > b) {
				swap(a, b);
			}
			edges[a].push_back(b);
			edges[b].push_back(a);
			if (a == 1) {
				isOne[b] = 1;
			}
			allEdges.emplace_back(a, b);
		}
		dfs(1);
	}
};

vector<pair<char, pair<int,int>>> operations;

void operation(char c, pair<int,int> edge) {
	operations.emplace_back(c, edge);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	
	Graph A = Graph();
	
	// 1) add edges 1-a
	for (int b : A.order) {
		if (b != 1 && !A.isOne[b]) {
			operation('+', {1, b});
		}
	}
	// 2) erase other edges
	for (pair<int,int> edge : A.allEdges) {
		if (edge.first != 1) {
			operation('-', edge);
		}
	}
	
	Graph B = Graph();
	// 3) add needed edges
	for (pair<int,int> edge : B.allEdges) {
		if (edge.first != 1) {
			operation('+', edge);
		}
	}
	// 4) erase edges 1-a backwards
	reverse(B.order.begin(), B.order.end());
	for (int b : B.order) {
		if (b != 1 && !B.isOne[b]) {
			operation('-', {1, b});
		}
	}
	
	cout << operations.size() << "\n";
	for (auto op : operations) {
		cout << op.first << " " << op.second.first << " " << op.second.second << "\n";
	}
}