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

const int N = 30005;

bitset<N> Current[N];
bitset<N> Needed2[N];
bitset<N> visited[2];

vector<int> Neighbours[N];
vector<pair<int, int>> Needed;
vector<pair<int, int>> Added;
vector<pair<int, int>> Original;
vector<pair<int, int>> toRemove;
vector<pair<char, pair<int, int>>> Solution;

void DFS(int u, int start)
{
    visited[u][0] = true;
    if(!Current[start][u] && u != start) {
        Added.push_back({start, u});
        Current[start][u] = 1;
        Current[u][start] = 1;
    }
    for(auto v : Neighbours[u]) {
        if(!visited[v][0])
            DFS(v, start);
    }
}

void DFS2(int u, int start)
{
    visited[u][1] = true;
    if(u != start && !Needed2[u][start] && Current[u][start]) {
        toRemove.push_back({start, u});
    }
    for(auto v : Neighbours[u]) {
        if(!visited[v][1] && Needed2[v][u])
            DFS2(v, start);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m1, m2, u, v;
    cin >> n;

    cin >> m1;
    for(int i = 0; i < m1; i++) {
        cin >> u >> v;
        Current[u][v] = 1;
        Current[v][u] = 1;
        Neighbours[u].push_back(v);
        Neighbours[v].push_back(u);
        Original.push_back({u, v});
    }
    cin >> m2;
    for(int i = 0; i < m2; i++) {
        cin >> u >> v;
        Needed.push_back({u, v});
        Needed2[u][v] = 1;
        Needed2[v][u] = 1;
    }

    DFS(1, 1);

    for(auto x : Needed) {
        if(!Current[x.first][x.second]) {
            Added.push_back({x.first, x.second});
            Current[x.first][x.second] = 1;
            Current[x.second][x.first] = 1;
        }
    }

    for(auto x : Added) {
        Solution.push_back({'+', {x.first, x.second}});
        Neighbours[x.first].push_back(x.second);
        Neighbours[x.second].push_back(x.first);
    }
    
    for(auto x : Original) {
        if(!Needed2[x.first][x.second]) {
            Solution.push_back({'-', {x.first, x.second}});
            Current[x.first][x.second] = 0;
            Current[x.second][x.first] = 0;
        }
    }
    DFS2(1, 1);
    for(int i = toRemove.size() - 1; i >= 0; i--)  
        Solution.push_back({'-', {toRemove[i].first, toRemove[i].second}});

    cout << Solution.size() << "\n";
    for(auto x : Solution) 
        cout << x.first << " " << x.second.first << " " << x.second.second << "\n";
}