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
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define st first
#define nd second
const int N = 3e4+3;
vector<int> grf[2][N];
vector<pair<char, pair<int, int>>> out;
bool odw1[N], odw2[N];
void dfs1(int v){
	odw1[v]=1;
	bool fnd=0;
	for(auto w:grf[0][v]){
		if(w==1) fnd=1;
	}
	if(v!=1 && !fnd) out.pb({'+', {1, v}});
	for(auto w:grf[0][v]){
		if(odw1[w]) continue;
		dfs1(w);
	}
}
bool fnd(int x, int i, int c){
	int p=0, k=grf[c][i].size(), m;
	while(p<k){
		m=(p+k)/2;
		if(grf[c][i][m]<x) p=m+1;
		else k=m;
	} 

	if(p==grf[c][i].size() || grf[c][i][p]!=x) return 0;
	return 1;
}
void upd(int i){
	for(auto w:grf[0][i]){
		if(w<i) continue;
		if(!fnd(w, i, 1)){
			out.pb({'-', {i, w}});
		}
	}
	for(auto w:grf[1][i]){
		if(w<i) continue;
		if(!fnd(w, i, 0)){
			out.pb({'+', {i, w}});
		}
	}
}
void dfs2(int v){
	odw2[v]=1;
	for(auto w:grf[0][v]){
		if(odw2[w]) continue;
		dfs2(w);
	}
	if(v==1) return;
	if(!fnd(1, v, 1)){
		out.pb({'-', {1, v}});
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	int m1, m2;
	cin >> m1;
	for(int i=0; i<m1; i++){
		int a, b;
		cin >> a >> b;
		grf[0][a].pb(b);
		grf[0][b].pb(a);
	}
	cin >> m2;
	for(int i=0; i<m2; i++){
		int a, b;
		cin >> a >> b;
		grf[1][a].pb(b);
		grf[1][b].pb(a);
	}
	for(int i=1; i<=n; i++){
		sort(grf[0][i].begin(), grf[0][i].end());
		sort(grf[1][i].begin(), grf[1][i].end());
	}
	dfs1(1);
	for(int i=2; i<=n; i++) upd(i);
	dfs2(grf[0][1][0]);
	cout << out.size() << '\n';
	for(auto o:out) cout << o.st << ' ' << o.nd.st << ' ' << o.nd.nd << '\n';
	return 0;
}