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

const int maxn = 2e5+1;
int m;
bool usedd[maxn];
bool iscut[maxn];
int h[maxn], d[maxn];
set <int> mset;
vector <string> ans;
void dfs(int v, vector <vector <int>> &g, int p = -1) {
    usedd[v] = 1;
    d[v] = h[v] = (p == -1 ? 0 : h[p] + 1);
    int children = 0;
    for (int u : g[v]) {
        if (u != p) {
            if (usedd[u])
                d[v] = min(d[v], h[u]);
            else {
                dfs(u, g, p);
                d[v] = min(d[v], d[u]);
                if (h[v] <= d[u] && p != -1) {
                    iscut[v] = 1;
                }
              	children++;
            }
        }
    }
    if (p == -1 && children > 1) {
        iscut[v] = 1;
    }
}



vector<char> used;

void dfs1 (int v, vector <vector <int>> &g, vector <vector <int>> &t) {
	used[v] = true;
	for (vector<int>::iterator i=g[v].begin(); i!=g[v].end(); ++i){
        if(!mset.count(*i) and *i != m)
    {
        ans.push_back('+' + to_string(*i+1) + " " + to_string(m+1));
        mset.insert(*i);
        t[m].push_back(*i);
        t[*i].push_back(m);
    }
		if (!used[*i])
			dfs1 (*i, g, t);
    }
}

set  <pair <int, int>> msett;

void dfs2 (int v, vector <vector <int>> &g, int p = -1) {
	used[v] = true;
	for (vector<int>::iterator i=g[v].begin(); i!=g[v].end(); ++i)
		if (!used[*i])
			dfs2(*i, g, v);
    pair <int, int> pp = {m, v};
    if(p!=m and msett.count(pp)==0)
    ans.push_back("- " + to_string(m+1) + " " + to_string(v+1));
}



int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m1, m2;
    cin >> n >> m1;
    vector <vector <int>> v1(n), v2(n);
    for(int i = 0; i < m1; i++){
        int x, y;
        cin >> x >> y;
        x--; y--;
        v1[x].push_back(y);
        v1[y].push_back(x);
    }
    cin >> m2;
    for(int i = 0; i < m2; i++){
        int x, y;
        cin >> x >> y;
        x--; y--;
        v2[x].push_back(y);
        v2[y].push_back(x);
    }

    dfs(0, v2);
    m = 0;
    vector <vector <int>> t(n);
    t = v1;
    for(int i = 0; i < n; i++)
    {
        if(!iscut[i]){
            m = i;
            break;
        }
    }
    for(auto x: v1[m])
        mset.insert(x);
    used.resize(n);
    dfs1(m, v1, t);
    set <pair <int,int>> e;
    for(int i = 0; i < n; i++)
        for(auto to: v2[i])
            if(to != m and i != m)
                e.insert({min(i, to), max(i, to)});
    set <pair <int,int>> d;
    for(int i = 0; i < n; i++)
        for(auto to: v1[i])
            if(e.count({min(i, to), max(i, to)}) == 0 and to != m and i != m)
                d.insert({min(i, to), max(i, to)});
    for(auto [a, b] : d)
        if(a != b)
            ans.push_back("- " + to_string(a+1) + " " + to_string(b+1));
    used.clear();
    used.resize(n);
    msett.clear();
    msett.insert({m, m});
    for(auto x: v1[m])
    msett.insert({m, x});
    dfs2(m,v2);
    cout << ans.size() << "\n";
    for(auto x: ans)
        cout << x << "\n";
    return 0;
}