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
//
// Created by BigBag on 13.03.2024 11:13:01
//

#include <bits/stdc++.h>

using namespace std;

#ifdef BigBag
#define DEBUG for (bool ____DEBUG = true; ____DEBUG; ____DEBUG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = 30333, inf = 1000111222;

int n, m[2];
vector<int> g[2][max_n];

vector<pair<char, pair<int, int>>> solve(int tp) {
    set<pair<int, int>> edges;
    vector<pair<char, pair<int, int>>> res;
    queue<int> q;
    q.push(0);
    vector<int> dist(n, inf);
    dist[0] = 0;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        if (dist[v] > 1) {
            res.push_back({'+', {0, v}});
            edges.insert({0, v});
            edges.insert({v, 0});
        }
        for (int to : g[tp][v]) {
            edges.insert({v, to});
            if (dist[to] == inf) {
                dist[to] = dist[v] + 1;
                q.push(to);
            }
        }
    }
    for (int v = 0; v < n; ++v) {
        for (int to : g[tp ^ 1][v]) {
            if (!edges.count({v, to})) {
                edges.insert({v, to});
                edges.insert({to, v});
                res.push_back({'+', {v, to}});
            }
        }
    }
    return res;
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < 2; ++i) {
        cin >> m[i];
        for (int j = 0; j < m[i]; ++j) {
            int u, v;
            cin >> u >> v;
            --u;
            --v;
            g[i][u].push_back(v);
            g[i][v].push_back(u);
        }
    }
    auto a = solve(0);
    auto b = solve(1);
    reverse(b.begin(), b.end());
    cout << a.size() + b.size() << "\n";
    for (auto [tp, p] : a) {
        auto [u, v] = p;
        cout << tp << " " << u + 1 << " " << v + 1 << "\n";
    }
    for (auto [tp, p] : b) {
        auto [u, v] = p;
        cout << char(tp ^ '+' ^ '-') << " " << u + 1 << " " << v + 1 << "\n";
    }
    return 0;
}