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


using namespace std;


vector <vector<int>> readGraph(int n) {
    vector <vector<int>> g(n);

    int m;
    cin >> m;

    while (m--) {
        int u, v;
        cin >> u >> v; u--; v--;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    return g;
}

struct op {
    bool add;
    int u, v;
};

vector <op> deconstruct(int n, vector <vector<int>> &g) {
    int root = 0;

    queue <int> q;
    q.push(root);

    vector <int> dist(n, -1);
    dist[root] = 0;

    while (!q.empty()) {
        int v = q.front(); q.pop();

        for (int u : g[v]) if (dist[u] == -1) {
            dist[u] = dist[v] + 1;

            q.push(u);
        }
    }

    vector <int> verts(n);
    iota(verts.begin(), verts.end(), 0);

    sort(verts.begin(), verts.end(), [&](int i, int j) {
        return dist[i] < dist[j];
    });

    vector <op> ops;
    for (int v : verts) if (dist[v] >= 2) {
        ops.push_back({true, root, v});
    }

    for (int v = 0; v < n; v++) if (v != root) {
        for (int u : g[v]) if (u != root && u < v) {
            ops.push_back({false, u, v});
        }
    }

    return ops;
}

vector <op> solve(int n, vector <vector<int>> &gStart, vector <vector<int>> &gEnd) {
    auto ops = deconstruct(n, gStart);
    auto opsEnd = deconstruct(n, gEnd);

    reverse(opsEnd.begin(), opsEnd.end());
    for (auto &o : opsEnd) {
        ops.push_back({!o.add, o.u, o.v});
    }

    return ops;
}

int main() {
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;

    auto gStart = readGraph(n);
    auto gEnd = readGraph(n);

    auto ops = solve(n, gStart, gEnd);

    cout << ops.size() << '\n';
    for (auto &o : ops) {
        char c = o.add ? '+' : '-';
        cout << c << ' ' << o.u + 1 << ' ' << o.v + 1 << '\n';
    }

    return 0;
}