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
#include <bits/stdc++.h>
#define boost                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
using pii = pair<int,int>;
struct Move {
    char ch;
    int a, b;
};

int ROOT = 1;

vector<Move> get_moves(int n) {
    int m;
    cin >> m;

    vector g(n+1, (vector<int>()));
    set<pii> edges;

    auto add_edge = [&](int a, int b) -> bool {
        if (a > b) swap(a, b);
        if (edges.count({a, b})) return false;
        edges.insert({a, b});
        return true;
    };

    while (m--) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
        add_edge(a, b);
    }

    vector<Move> res;
    vector vis(n+1, 0);
    auto put_edges = [&](int v, auto &&put_edges) -> void {
        vis[v] = 1;
        if (v != ROOT) {
            if (add_edge(ROOT, v)) res.emplace_back('+', ROOT, v);
        }
        for (auto u : g[v]) {
            if (!vis[u]) put_edges(u, put_edges);
        }
    };

    put_edges(ROOT, put_edges);

    // Root is connected to everything now, remove all edges
    for (auto [a, b] : edges) {
        if (a != 1 && b != 1) {
            res.emplace_back('-', a, b);
        }
    }

    return res;
}

int32_t main() {
    boost;
    int n;
    cin >> n;
    vector<Move> moves_to_star = get_moves(n);
    vector<Move> moves_from_star = get_moves(n);

    reverse(ALL(moves_from_star));
    for (auto &i : moves_from_star) i.ch = (i.ch == '+' ? '-' : '+');

    int r = moves_to_star.size() + moves_from_star.size();
    cout << r << "\n";
    for (auto i : moves_to_star) cout << i.ch << " " << i.a << " " << i.b << "\n";
    for (auto i : moves_from_star) cout << i.ch << " " << i.a << " " << i.b << "\n";
}