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
127
128
129
130
131
132
133
134
135
//
// Created by piotr on 12.03.2024.
//
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <list>
#include <vector>
#include <set>
#include <stack>
#include <queue>

struct Molecule {
public:
	std::vector<std::set<int>> neighbors;
	std::vector<std::pair<int,int>> edges;

	Molecule(int size)
			:neighbors(size) { }

	void read()
	{
		int M;
		assert(scanf("%d", &M)==1);
		while (M-- > 0) {
			int a, b;
			assert(scanf("%d%d", &a, &b) == 2);
			--a, --b;
			neighbors[a].insert(b);
			neighbors[b].insert(a);
			if (a > b) {
				std::swap(a, b);
			}
			edges.push_back({a, b});
		}
		std::sort(edges.begin(), edges.end());
	}
};

struct Command
{
	char op;
	int a, b;
};

template<class T>
void bfs(const Molecule& molecule, int root, T& results) {
	std::queue<int> queue;
	std::vector<bool> visited(molecule.neighbors.size(), false);
	visited[root] = true;
	for (int w : molecule.neighbors[root]) {
		queue.push(w);
	}
	while (!queue.empty()) {
		int v = queue.front();
		queue.pop();
		if (visited[v]) {
			continue;
		}
		results.push(v);
		visited[v] = true;

		for (int w : molecule.neighbors[v]) {
			if (!visited[w]) {
				queue.push(w);
			}
		}
	}
}

int main()
{
	int N;
	assert(scanf("%d", &N)==1);
	Molecule before(N), after(N);
	before.read();
	after.read();

	std::list<std::pair<int,int>> edges_to_add;
	std::list<std::pair<int,int>> edges_to_remove;
	std::set_difference(
			after.edges.begin(), after.edges.end(),
			before.edges.begin(), before.edges.end(),
			std::back_inserter(edges_to_add)
	);
	std::set_difference(
			before.edges.begin(), before.edges.end(),
			after.edges.begin(), after.edges.end(),
			std::back_inserter(edges_to_remove)
	);

	std::list<Command> commands;
	const int root = 0; // jeśli to zmienimy, musimy uważać niżej ze sprawdzaniem zarówno e.first jak i e.second

	// KROK 1. Dodajemy tymczasowe krawędzie od roota (0) do wszystkich innych w odpowiedniej kolejności
	std::queue<int> before_root_order;
	bfs(before, root, before_root_order);
	while (!before_root_order.empty()) {
		int w = before_root_order.front();
		before_root_order.pop();
		if (!before.neighbors[root].count(w)) {
			commands.push_back({'+', root, w});
		}
	}

	// KROK 2. Dodajemy te krawędzie, których brakuje, niedotykające roota
	for (auto e : edges_to_add) {
		if (e.first != root) {
			commands.push_back({'+', e.first, e.second});
		}
	}

	// KROK 3. Usuwamy te krawędzie, które powinny zniknąć, niedotykające roota
	for (auto e : edges_to_remove) {
		if (e.first != root) {
			commands.push_back({'-', e.first, e.second});
		}
	}

	// KROK 4. Usuwamy niepotrzebne krawędzie od roota (0) do wszystkich innych w odpowiedniej kolejności
	std::stack<int> after_root_order;
	bfs(after, root, after_root_order);
	while (!after_root_order.empty()) {
		int w = after_root_order.top();
		after_root_order.pop();
		if (!after.neighbors[root].count(w)) {
			commands.push_back({'-', w, root});
		}
	}

	printf("%lu\n", commands.size());
	for (const auto& command : commands) {
		printf("%c %d %d\n", command.op, command.a+1, command.b+1);
	}
}