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

constexpr int MAX_N = 30000;
constexpr int MAX_M = 50000;
constexpr int MAX_RES = 200000;

bool keep_root[MAX_N];

std::pair<short, short> src_list[MAX_M+1], dest_list[MAX_M+1];

int res_size;
struct {char op; short a, b;} res[MAX_RES];

std::vector<short> src_adjacent[MAX_N], dest_adjacent[MAX_N];

bool visited[MAX_N];

void dfs(const short v, const bool preorder, const std::vector<short> tree[])
{
	visited[v] = true;
	if(preorder && !keep_root[v])
		res[res_size++] = {'+', 1, v+1};
	for(const short x : tree[v])
		if(!visited[x])
			dfs(x, preorder, tree);
	if(!preorder && !keep_root[v])
		res[res_size++] = {'-', 1, v+1};
}

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

	int n;
	std::cin >> n;

	int ms;
	std::cin >> ms;

	visited[0] = keep_root[0] = true;
	for(int i = 0; i < ms; ++i)
	{
		int a, b;
		std::cin >> a >> b;
		--a, --b;
		if(a > b) std::swap(a, b);
		if(a == 0) keep_root[b] = true;
		src_list[i] = {a, b};
		src_adjacent[a].push_back(b);
		src_adjacent[b].push_back(a);
	}

	dfs(0, true, src_adjacent);

	int md;
	std::cin >> md;

	for(int i = 1; i < n; ++i)
		visited[i] = keep_root[i] = false;
	for(int i = 0; i < md; ++i)
	{
		int a, b;
		std::cin >> a >> b;
		--a, --b;
		if(a > b) std::swap(a, b);
		if(a == 0) keep_root[b] = true;
		dest_list[i] = {a, b};
		dest_adjacent[a].push_back(b);
		dest_adjacent[b].push_back(a);
	}

	std::sort(src_list, src_list+ms);
	std::sort(dest_list, dest_list+md);
	src_list[ms] = dest_list[md] = {0x7FFF, 0x7FFF};

	int scnt = src_adjacent[0].size(), dcnt = dest_adjacent[0].size();
	while(scnt < ms || dcnt < md)
	{
		if(src_list[scnt] < dest_list[dcnt])
		{
			res[res_size++] = {'-', src_list[scnt].first+1, src_list[scnt].second+1};
			++scnt;
		}
		else if(src_list[scnt] > dest_list[dcnt])
		{
			res[res_size++] = {'+', dest_list[dcnt].first+1, dest_list[dcnt].second+1};
			++dcnt;
		}
		else // src_list[scnt] == dest_list[dcnt]
			++scnt, ++dcnt;
	}

	dfs(0, false, dest_adjacent);

	std::cout << res_size << '\n';
	for(int i = 0; i < res_size; ++i)
		std::cout << res[i].op << ' ' << res[i].a << ' ' << res[i].b << '\n';

	return 0;
}