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;

typedef long long ll;
typedef pair<ll, ll> pll;

struct plla {
    ll first, second;
    bool add;
};

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

    ll n;
    cin >> n;
    vector<vector<ll>> graph(n, vector<ll>());
    map<pll, bool> edges;
    ll m1, m2;
    cin >> m1;
    for (ll i = 0; i < m1; i++) {
        ll from, to;
        cin >> from >> to;
        from--; to--;
        graph[from].push_back(to);
        graph[to].push_back(from);
        edges[(from < to ? make_pair(from, to) : make_pair(to, from))] = false;
    }
    cin >> m2;
    for (ll i = 0; i < m2; i++) {
        ll from, to;
        cin >> from >> to;
        from--; to--;
        if (edges.count((from < to ? make_pair(from, to) : make_pair(to, from))) == 0) {
            edges[(from < to ? make_pair(from, to) : make_pair(to, from))] = true;
        }else {
            edges.erase(from < to ? make_pair(from, to) : make_pair(to, from));
        }
    }
    queue<ll> q;
    vector<ll> dist(n, -1);
    q.push(0);
    dist[0] = 0;
    vector<plla> artificial;
    while (!q.empty()) {
        ll v = q.front();
        q.pop();
        for (ll u : graph[v]) {
            if (dist[u] == -1) {
                dist[u] = dist[v] + 1;
                if (dist[u] > 1) {
                    graph[0].push_back(u);
                    graph[u].push_back(0);
                    if (edges.count(make_pair(0, u)) != 0 && edges[make_pair(0, u)]) {
                        edges.erase(make_pair(0, u));
                        artificial.push_back({0, u, true});
                    }else {
                        artificial.push_back({0, u, false});
                    }
                }
                q.push(u);
            }
        }
    }
    vector<plla> ans;
    for (auto &e : artificial) {
        ans.push_back({e.first, e.second, true});
    }
    vector<pll> temp1;
    vector<pll> temp2;
    for (auto &e : edges) {
        if (e.second) {
            temp1.emplace_back(e.first.first, e.first.second);
        }else {
            temp2.emplace_back(e.first.first, e.first.second);
        }
    }
    for (auto &e : temp1) {
        ans.push_back({e.first, e.second, true});
    }
    for (auto &e : temp2) {
        ans.push_back({e.first, e.second, false});
    }
    for (auto &e : artificial) {
        if (!e.add) {
            ans.push_back({e.first, e.second, false});
        }
    }
    cout << ans.size() << "\n";
    for (auto &a : ans) {
        cout << (a.add ? '+' : '-') << " " << a.first + 1 << " " << a.second + 1 << "\n";
    }




}