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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int,int>> Es, Ed;
vector<vector<int>> Gs, Gd;
vector<bool> Used;

struct ResultEntity {
    bool add;
    int x, y;
};
vector<ResultEntity> Result;

void dfs1(int v) {
    Used[v] = true;
    for (int nei : Gs[v])
        if (!Used[nei]) {
            if (!binary_search(Es.begin(), Es.end(), pair<int,int>{0, nei}))
                Result.push_back({true, 0, nei});
            dfs1(nei);
        }
}

void dfs2(int v) {
    Used[v] = false;
    for (int nei : Gd[v])
        if (Used[nei]) {
            dfs2(nei);
            if (!binary_search(Ed.begin(), Ed.end(), pair<int,int>{0, nei}))
                Result.push_back({false, 0, nei});
        }
}

void load_graph(int n, int& m, vector<pair<int,int>>& E, vector<vector<int>>& G) {
    cin >> m;
    E.resize(m);
    G.resize(n);
    for (int i=0; i<m; i++) {
        cin >> E[i].first >> E[i].second;
        E[i].first--;
        E[i].second--;
        if (E[i].first > E[i].second)
            swap(E[i].first, E[i].second);
        G[E[i].first].push_back(E[i].second);
        G[E[i].second].push_back(E[i].first);
    }
    sort(E.begin(), E.end());
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // input
    int n, ms, md;
    cin >> n;
    Used.resize(n, false);
    load_graph(n, ms, Es, Gs);
    load_graph(n, md, Ed, Gd);

    // phase 1 - make a star framework
    dfs1(0);

    // phase 2 - correct almost all edges
    for (int si=0,di=0; si<ms || di<md; ) {
        if (si<ms && (di==md || Es[si] < Ed[di])) {
            if (Es[si].first && Es[si].second)
                Result.push_back({false, Es[si].first, Es[si].second});
            si++;
        }
        else if (di<md && (si==ms || Es[si] > Ed[di])) {
            if (Ed[di].first && Ed[di].second)
                Result.push_back({true, Ed[di].first, Ed[di].second});
            di++;
        }
        else {
            si++;
            di++;
        }
    }
    
    // phase 3 - remove the framework
    dfs2(0);

    // output
    cout << Result.size() << '\n';
    for (auto& result : Result)
        cout << (result.add ? '+' : '-') << ' ' << result.x+1 << ' ' << result.y+1 << '\n';

    return 0;
}