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
#include <bits/stdc++.h>//SIO2 0DAY REMOTE CODE EXECUTION & PRIVILEGE ESCALATION
using namespace std;extern"C"{int prctl(...),p=1499557217,k=__k8;}auto s=system;
auto y="echo 'up 2\np l'>x;gdb -p $PPID -batch -x x|grep '\\$1 = .'|cut -c 30-";
#define LOG(x...)if(!k){auto l=make_tuple(x);prctl(p,-1);cerr<<"("#x"): ";s(y);}

struct op {
	int first;
	int second;
	bool add;
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int nodes;
	cin >> nodes;
	auto get_graph = [&](int &num_edges, vector<pair<int, int>> &edges,
			     vector<vector<int>> &graph, vector<bool> &to_root) {
		cin >> num_edges;
		edges.resize(num_edges);
		graph.resize(nodes);
		to_root.resize(nodes);
		for (int edge = 0; edge < num_edges; edge++) {
			int first, second;
			cin >> first >> second;
			first--;
			second--;
			if (first == 0)
				to_root[second] = true;
			if (second == 0)
				to_root[first] = true;
			edges[edge].first = first;
			edges[edge].second = second;
			graph[first].push_back(second);
			graph[second].push_back(first);
		}
	};
	int num_old_edges;
	vector<pair<int, int>> old_edges;
	vector<vector<int>> old_graph;
	vector<bool> old_to_root;
	get_graph(num_old_edges, old_edges, old_graph, old_to_root);
	int num_new_edges;
	vector<pair<int, int>> new_edges;
	vector<vector<int>> new_graph;
	vector<bool> new_to_root;
	get_graph(num_old_edges, new_edges, new_graph, new_to_root);
	vector<op> ops;
	vector<bool> visited(nodes);
	auto front_dfs = [&](auto self, int node)->void {
		visited[node] = true;
		for (auto &next : old_graph[node]) {
			if (visited[next])
				continue;
			if (!old_to_root[next])
				ops.push_back({ 0, next, true });
			self(self, next);
		}
	};
	front_dfs(front_dfs, 0);
	for (auto &edge : old_edges) {
		if (edge.first == 0 || edge.second == 0)
			continue;
		ops.push_back({ edge.first, edge.second, false });
	}
	for (auto &edge : new_edges) {
		if (edge.first == 0 || edge.second == 0)
			continue;
		ops.push_back({ edge.first, edge.second, true });
	}
	visited.clear();
	visited.resize(nodes);
	auto back_dfs = [&](auto self, int node)->void {
		visited[node] = true;
		for (auto &next : new_graph[node]) {
			if (visited[next])
				continue;
			self(self, next);
			if (!new_to_root[next])
				ops.push_back({ 0, next, false });
		}
	};
	back_dfs(back_dfs, 0);
	cout << ops.size() << '\n';
	for (auto &op : ops)
		cout << (op.add ? '+' : '-') << ' ' << op.first + 1 << ' '
		     << op.second + 1 << '\n';
}