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
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ssize(x) int(x.size())
int inf=1000000000;

int INT() {
	int in; scanf("%d", &in);
	return in;
}

struct edge {
	int a, b;
};

int n;

void bfs_star(vector <vector <int> > &g, vector <edge> &oper) {
	vector <int> dist(n+1, inf);
	dist[1]=0;
	queue <int> q;
	q.push(1);
	while(!q.empty()) {
		int x=q.front();
		q.pop();
		int d=dist[x]+1;
		for(int &u : g[x]) if(dist[u]>d) {
			dist[u]=d, q.push(u);
			if(d>1) oper.pb({1, u});
		}
	}
}

int main() {
	n=INT();
	int m1=INT();
	vector <vector <int> > g1(n+1), g2(n+1);
	for(int i=0; i<m1; ++i) {
		int a=INT(), b=INT();
		g1[a].pb(b), g1[b].pb(a);
	}
	int m2=INT();
	for(int i=0; i<m2; ++i) {
		int a=INT(), b=INT();
		g2[a].pb(b), g2[b].pb(a);
	}
	vector <edge> star1, star2;
	bfs_star(g1, star1), bfs_star(g2, star2);
	reverse(star2.begin(), star2.end());
	map <pair <int, int>, bool> e1, e2;
	for(int x=2; x<=n; ++x) for(int &u : g1[x]) if(u>x) e1[mp(x, u)]=1;
	for(int x=2; x<=n; ++x) for(int &u : g2[x]) if(u>x) e2[mp(x, u)]=1;
	
	vector <edge> add, rem;
	for(int x=2; x<=n; ++x) for(int &u : g2[x]) if(u>x && !e1.contains(mp(x, u))) add.pb({x, u});
	for(int x=2; x<=n; ++x) for(int &u : g1[x]) if(u>x && !e2.contains(mp(x, u))) rem.pb({x, u});
	
	printf("%d\n", ssize(star1)+ssize(add)+ssize(rem)+ssize(star2));
	for(edge &e : star1) printf("+ %d %d\n", e.a, e.b);
	for(edge &e : add) printf("+ %d %d\n", e.a, e.b);
	for(edge &e : rem) printf("- %d %d\n", e.a, e.b);
	for(edge &e : star2) printf("- %d %d\n", e.a, e.b);
	exit(0);
}