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

#define DebugOn false
#define err if constexpr(DebugOn) cerr
bitset<30'001> visited;
vector<int> edges[30'001];
set<pair<int,int>> edgeis;
vector<int> end_edges[30'001];
set<pair<int,int>> end_edgeis;

vector<tuple<bool,int, int>> out;

void addto1(int k){
    if(visited[k] or k==1)return;
    visited[k]=1;
    if(!edgeis.count({1,k})) {out.push_back({1,1,k});
        edgeis.insert({1,k});
        edgeis.insert({k,1});
    };
    for(auto j : edges[k]){
        addto1(j);
    }
}
int main(){
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int m;
    cin >> m;
    for(int i = 0; i < m; i++){
        int a,b;
        cin >> a >> b;
        edges[a].push_back(b);
        edges[b].push_back(a);
        edgeis.insert({a,b});
        edgeis.insert({b,a});
    }
    err << "Progress [1/10]\n";
    cin >> m;
    for(int i = 0; i < m; i++){
        int a,b;
        cin >> a >> b;
        end_edges[a].push_back(b);
        end_edges[b].push_back(a);
        end_edgeis.insert({a,b});
        end_edgeis.insert({b,a});
    }
    err << "Progress [2/10]\n";
    for(auto k : edges[1]){
        addto1(k);
    }
    err << "Progress [3/10]\n";
    for(auto k : end_edgeis){
        if(!edgeis.count(k)){
            out.push_back({1,k.first,k.second});
            edgeis.insert({k.first,k.second});
            edgeis.insert({k.second,k.first});
        }
    }
    err << "Progress [4/10]\n";
    for(auto k : edgeis){
        if(!end_edgeis.count(k) and k.first < k.second){
            out.push_back({0,k.first,k.second});
            //edgeis.erase({k.first,k.second});
            //edgeis.erase({k.second,k.first});
        }
    }
    err << "Progress [5/10]\n";

    cout << out.size()<<'\n';
    for(auto k : out){
        cout << (get<0>(k)?'+':'-') << ' ' << (get<1>(k))<<' ' <<get<2>(k)<<'\n';
    }
    err << "Progress [6/10]\n";
}