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
136
137
138
139
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <list>
using namespace std;

int moves;
vector<string> moves_vec;

void printAddEdge(int a, int b) {
	moves++;
	string x = "+ ";
	x+=to_string(a+1);
	x+=" ";
	x+=to_string(b+1);
	moves_vec.push_back(x);
}
void printDelEdge(int a, int b) {
	moves++;
	string x = "- ";
	x+=to_string(a+1);
	x+=" ";
	x+=to_string(b+1);
	moves_vec.push_back(x);
}
class Graph {
public:
  vector<vector<int>> adjlist;
  set<pair<int,int>> edges_set;
  set<pair<int,int>> edges_ones_set;
  vector<int> bfs_dist;
  map<int, vector<int>> dist_to_list;
  int n;
  Graph(int size_) {
  	n = size_;
    adjlist.resize(size_);
	bfs_dist.resize(size_, size_+1);
  }

  void addEdge(int a, int b) {
  	int src = a - 1;
  	int dst = b - 1;
  	if (src > dst) {swap(src, dst);}
    adjlist[src].push_back(dst);
    adjlist[dst].push_back(src);
  	edges_set.insert({src, dst});
  	if (src == 0) {
  		edges_ones_set.insert({src, dst});
  	}
  }
  void BFS1 (int source) {
    queue<int> Q;
    bfs_dist[source] = 0;
    Q.push(source);
    while (!Q.empty()) {
        int node = Q.front();
        Q.pop();
        for (auto& adj_node : adjlist[node]) {
            if (bfs_dist[adj_node] == n+1) {
                bfs_dist[adj_node] = bfs_dist[node] + 1;
                if (!edges_set.count({0, adj_node})) {
                	printAddEdge(0, adj_node);
                }
                Q.push(adj_node);
            }
        }
   }
  }
  void BFS2 (int source) {
    queue<int> Q;
    bfs_dist[source] = 0;
    Q.push(source);
    while (!Q.empty()) {
        int node = Q.front();
        Q.pop();
        for (auto& adj_node : adjlist[node]) {
            if (bfs_dist[adj_node] == n+1) {
                bfs_dist[adj_node] = bfs_dist[node] + 1;
                dist_to_list[bfs_dist[adj_node]].push_back(adj_node);
                Q.push(adj_node);
            }
        }
   }
  }  
};

int main() {
	int n, m1, m2;
	cin >> n;
	Graph g1(n);
	Graph g2(n);
	cin >> m1;
	for (int i = 0; i < m1; i++) {
		int x, y;
		cin >> x >> y;
		g1.addEdge(x, y);
	}
	cin >> m2;
	for (int i = 0; i < m2; i++) {
		int x, y;
		cin >> x >> y;
		g2.addEdge(x, y);
	}
	set<pair<int,int>> result_to_delete;
	set<pair<int,int>> result_to_add;
	auto s1 = g1.edges_set;
	auto s2 = g2.edges_set;
	std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
    std::inserter(result_to_delete, result_to_delete.end()));
	std::set_difference(s2.begin(), s2.end(), s1.begin(), s1.end(),
    std::inserter(result_to_add, result_to_add.end()));
	g1.BFS1(0);
	for(const auto&[a, b]: result_to_delete) {
		if (a != 0) {
			printDelEdge(a, b);
		}
	}
	for(const auto&[a, b]: result_to_add) {
		if (a != 0) {
			printAddEdge(a, b);
		}
	}
	g2.BFS2(0);
	for (auto it: g2.dist_to_list) {
		for (int k: it.second) {
			if (g2.edges_ones_set.count({0, k}) == 0) {
				printDelEdge(0, k);
			}
		}
	}
	cout << moves << endl;
	for (const auto& x : moves_vec) {
		cout << x << endl;
	}
	return 0;
}