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
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;

constexpr int M = 3e4+7;

int n, m1, m2;
vector<int> G[M];
set<PII> kraw; //krawedzie w orginalnej czasteczce
set<PII> fin; //krawedzie w finalnej czasteczce
bitset<M> exist[M];

vector<int> order;
int vis[M];

vector<pair<char, PII>> ans;

void DFS(int v){
	order.push_back(v);
	vis[v] = 1;
	for(auto i : G[v]){
		if(vis[i]) continue;
		DFS(i);
	} 
}

void update(char c, int a, int b){
	if(c == '+') exist[a][b] = exist[b][a] = 1;
	else exist[a][b] = exist[b][a] = 0;
	ans.push_back({c,{a,b}});
}

void init(){
	order.clear();
	for(int i=1; i<=n; i++){
		G[i].clear();
		vis[i] = 0;
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n;
	
	cin >> m1;
	
	for(int i=1; i<=n; i++) exist[i][i] = 1;
	for(int i=0; i<m1; i++){
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
		kraw.insert({min(a,b), max(a,b)});
		exist[a][b] = exist[b][a] = 1;
	}
	
	//dodanie z 1 do kazdego innego
	DFS(1); 
	for(auto i : order){
		if(exist[1][i] == 0) update('+',1,i);
	}
	
	//dodanie co potrzeba w finalnej czasteczce
	cin >> m2;
	init();
	for(int i=0; i<m2; i++){
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
		fin.insert({min(a,b), max(a,b)});
		if(exist[a][b] == 0) update('+',a,b);
	}
	
	//wyrzucenie tego co nie potrzeba z orginalnej czasteczki (poza krawedziami z 1)
	for(auto i : kraw){
		if(i.first == 1 || i.second == 1) continue;
		if(fin.find(i) == fin.end()) update('-',i.first, i.second);
	}
	
	//wyrzucenie zbednych polaczen miedzy 1 a kazdym innym
	DFS(1);
	for(int i=order.size()-1; i>0; i--){
		if(fin.find({1,order[i]}) == fin.end()) update('-',1,order[i]);
	}
	
	cout << ans.size() << '\n';
	
	for(auto i : ans) cout << i.first << ' ' << i.second.first << ' ' << i.second.second << '\n';
		
	return 0;
}