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
#include <iostream>
#include <vector>
#include <set>

using namespace std;
set <int> bajt[50007], endx[50007];
bool odw[50007], odw2[50007];
vector <int> V;
vector <int> V2;
int n,q,x,y,counter=0;
string s;
void dfs(int x){
    V.push_back(x);
    odw[x] = true;
    for(auto it : bajt[x]){
        if(!odw[it]){
            dfs(it);
        }
    }
}
void dfs2(int x){
    V2.push_back(x);
    odw2[x] = true;
    for(auto it : endx[x]){
        if(!odw2[it]){
            dfs2(it);
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>q;
    for(int i=0;i<q;i++){
        cin>>x>>y;
        bajt[x].insert(y);
        bajt[y].insert(x);
    }
    dfs(1);
    for(int i=1;i<V.size();i++){
        if(bajt[1].find(V[i]) == bajt[1].end()){
            bajt[1].insert(V[i]);
            bajt[V[i]].insert(1);
            s += "+ " + to_string(1) + " "+ to_string(V[i]) + "\n";
            ++counter;
        }
    }
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x>>y;
        endx[x].insert(y);
        endx[y].insert(x);
        if(bajt[x].find(y) == bajt[x].end()){
            bajt[x].insert(y);
            bajt[y].insert(x);
            s += "+ " + to_string(x) + " " + to_string(y) + "\n";
            ++counter;
        }
    }
    dfs2(1);
    for(int i=2;i<=n;i++){
        vector<int> toDelete;
        for(auto it : bajt[i]) {
            if(endx[i].find(it) == endx[i].end() && it != 1) {
                toDelete.push_back(it);
                s += "- " + to_string(it) + " " + to_string(i) + "\n";
                ++counter;
            }
        }   
        for(auto it : toDelete) {
            bajt[i].erase(it);
            bajt[it].erase(i);
        }
    }
    for(int i=V2.size()-1;i>=1;i--){
        if(endx[1].find(V2[i]) == endx[1].end()){
            s += "- " + to_string(V2[i]) + " " + to_string(1) + "\n";
            ++counter;
            bajt[1].erase(V2[i]);
            bajt[V2[i]].erase(1);
        }
    }
    cout<<counter<<endl;
    cout<<s;
    return 0;
}