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
//GRT_2018
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define all(x) x.begin(), x.end()
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

vector<tuple<int,int,int>> toStar(vector<vi> g) {
    vector<tuple<int,int,int>>op;
    set<pi>edg;
    for (int u = 0; u < (int)g.size(); ++u) {
        for (int v : g[u]) {
            edg.insert({u, v});
        }
    }
    
    vector<bool> vis((int)g.size());
    fill(all(vis), false);

    auto dfs = [&](int u, auto&& dfs) -> void {
        vis[u] = true;
        for (int v : g[u]) {
            if (!vis[v]) {
                if (!edg.count({0, v})) {
                    op.emplace_back(1, 0, v);
                }
                dfs(v, dfs);
            }
        }
    };

    dfs(0, dfs);

    for (auto [a,b] : edg) {
        if (a < b && a != 0) {
            op.emplace_back(-1, a, b);
        }
    }

    return op;
}

void revert(vector<tuple<int,int,int>> &op) {
    for (auto &[a,b,c] : op) {
        a = -a;
    }
    reverse(all(op));
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
    
    int n, ms, md;
    cin >> n;

    vector<vi>gs(n), gm(n);

    cin >> ms;

    for (int a, b, i = 0; i < ms; ++i) {
        cin >> a >> b;
        a--, b--;
        gs[a].PB(b);
        gs[b].PB(a);
    }

    cin >> md;

    for (int a, b, i = 0; i < md; ++i) {
        cin >> a >> b;
        a--, b--;
        gm[a].PB(b);
        gm[b].PB(a);
    }

    auto one = toStar(gs);
    auto two = toStar(gm);

    revert(two);

    for (auto x : two) one.PB(x);

    cout << (int)one.size() << "\n";

    for (auto [a,b,c] : one) {
        cout << (a > 0 ? '+' : '-') << " " << b + 1 << " " << c + 1 << "\n";
    }

}