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

using namespace std;
typedef pair<int,int> pii;
struct graph{
	vector<vector<pair<int,int>>> v; vector<int> odw;
	vector<vector<int> > v2;
	vector<int> fake; struct st2{int a, b;}; vector<st2> kraw;
	struct wynik{char znak; int a,b;}; vector<wynik> wyn;
	
	void IN(int n){
		v.resize(n + 1); odw.resize(n + 1); v2.resize(n + 1);
	}
	void ADD(int a, int b, int nr, bool rodz){
		v[a].emplace_back(b, nr);
		v[b].emplace_back(a,nr);
		kraw.emplace_back(a,b);
	}
	void ADD2(int a, int b){
		v2[a].emplace_back(b);
		v2[b].emplace_back(a);
	}
	void sortall(int n){
		for(int i = 1; i <= n; ++i) sort(v[i].begin(), v[i].end());
	}
	
	
	queue<pair<int,int>> q; int NR = 0;
    void bfs_add(int x, int d, map<pair<int,int>, bool> &mp){
        ++NR; odw[x] = NR; q.push({x, 0});
        while(!q.empty()){
            x = q.front().first; d = q.front().second; odw[x] = NR;
            if(d >= 2){
                if(v[x][0].first != 1){
                    wyn.emplace_back('+',1,x);
                    mp[{1,x}] = 1;
                    fake.emplace_back(kraw.size()); kraw.emplace_back(1, x);
                }
            } q.pop();
            for(int j = 0; j < (int)v[x].size(); ++j){
                if(odw[v[x][j].first] != NR){q.push({v[x][j].first, d + 1}); odw[v[x][j].first] = NR;}
            }
        }
    }
	
	void fix(int n, map<pair<int,int>,bool> &mp, map<pair<int,int>,bool> &mp2){
		int a, b; 
		for(int i = 1; i <= n; ++i){
			for(int j = 0; j <(int)v2[i].size(); ++j){
				if(i > v2[i][j]) continue;
				a = i; b = v2[i][j];
				if(mp.find({a,b}) == mp.end()) {
					wyn.emplace_back('+',a,b);
				}
			}
		}
		
		for(int i = 1; i <= n; ++i){
			for(int j = 0; j <(int)v[i].size(); ++j){
				if(i > v[i][j].first) continue;
				a = i; b = v[i][j].first;
				if(mp2.find({a,b}) == mp2.end()){	
					if(a != 1) wyn.emplace_back('-',a,b);
				}
			}
		}
		
		queue<pii> q; vector<pii> usuwam; q.push({1,0}); int x, d; ++NR; odw[1] = NR;
        while(!q.empty()){
            x = q.front().first; d = q.front().second; odw[x] = NR;
            if(d >= 2) usuwam.emplace_back(d, x);
            q.pop();
            for(int i = 0; i < (int)v2[x].size(); ++i){
                if(odw[v2[x][i]] != NR){q.push({v2[x][i], d + 1}); odw[v2[x][i]] = NR;}
            }
        }
		reverse(usuwam.begin(), usuwam.end());
		for(int i = 0; i < (int)usuwam.size(); ++i){
			a = 1; b = usuwam[i].second;
			if(mp2.find({1,b}) == mp2.end()){
				wyn.emplace_back('-',a,b);
			}
		}
	}

	void WYNIK(){
		cout << wyn.size() << "\n";
		for(int i = 0; i < (int)wyn.size(); ++i){
			cout << wyn[i].znak << " " << wyn[i].a << " " << wyn[i].b << "\n";
		}
	}
	
};
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m; cin >> n >> m;
	graph F; F.IN(n); int a, b;
	map<pair<int,int>, bool> mp1, mp2;
	for(int i = 0; i < m; ++i){
		cin >> a >> b; F.ADD(a,b,0,0);
		if(a > b) swap(a,b);
		mp1[{a,b}] = 1;
	} 
	F.bfs_add(1, 0, mp1);
	
	int m2; cin >> m2;
	for(int i = 0; i < m2; ++i){
		cin >> a >> b;
		if(a > b) swap(a,b); 
		F.ADD2(a,b);
		
		mp2[{a,b}] = 1;
	} F.fix(n, mp1, mp2);
	F.WYNIK();

}