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
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define st first
#define nd second
typedef long long ll;
using namespace std;
vector<vector<int>> g1, g2;
vector<pair<int, int>> e1, e2;
vector<pair<int, int>> add, remov;
vector<bool> vis;

void dfs1(int u) {
    vis[u] = true;
    for (int v: g1[u]) {
        if (vis[v]) continue;
        if (!binary_search(e1.begin(), e1.end(), make_pair(1, v))) add.push_back({1, v});
        dfs1(v);
    }
}

void dfs2(int u) {
    vis[u] = true;
    for (int v: g2[u]) {
        if (vis[v]) continue;
        dfs2(v);
        if(!binary_search(e2.begin(), e2.end(), make_pair(1, v))) remov.push_back({1, v});
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m1, m2; cin >> n >> m1;
    g1 = g2 = vector<vector<int>>(n+1);
    e1.resize(m1);
    for (int i = 0; i < m1; i++) {
        int a, b; cin >> a >> b;
        if (a>b) swap(a, b);
        e1[i] = {a, b};
        g1[a].push_back(b);
        g1[b].push_back(a);
    }
    cin >> m2;
    e2.resize(m2);
    for (int i = 0; i < m2; i++) {
        int a, b; cin >> a >> b;
        if (a>b) swap(a, b);
        e2[i] = {a, b};
        g2[a].push_back(b);
        g2[b].push_back(a);
    }
    sort(e1.begin(), e1.end());
    sort(e2.begin(), e2.end());
    vis = vector<bool>(n+1, false);
    dfs1(1);
    for (auto e: e2) {
        if (e.st != 1 && !binary_search(e1.begin(), e1.end(), e)) add.push_back(e);
    }
    for (auto e: e1) {
        if (e.st != 1 && !binary_search(e2.begin(), e2.end(), e)) remov.push_back(e);
    }
    vis = vector<bool>(n+1, false);
    dfs2(1);
    cout << add.size() + remov.size() << "\n";
    for (auto e: add) cout << "+ " << e.st << ' ' << e.nd << '\n';
    for (auto e: remov) cout << "- " << e.st << ' ' << e.nd << '\n';
}