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
// https://sio2.mimuw.edu.pl/c/pa-2024-1/p/alc/
#include <bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rep(i, a) for (int i = 0; i < (a); i++)
#define rep1(i, a) for (int i = 1; i <= (a); i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
const int MAX_N = 3e4 + 5;
set<int> ruszt; // dfs laczy wszystko z v1, potem demontuje zbedne krawedzie
bool vis[MAX_N], v2[MAX_N];
set<pi> g1, g2;
vector<int> g[MAX_N], gg[MAX_N];
vector<string> ans;
void dfs(int v) {
    // cerr << "dfs" << v << '\n';
    if (vis[v])
        return;
    vis[v] = 1;
    // cerr << " r";
    if (ruszt.find(v) == ruszt.end()) {
        ans.pb("+ 1 " + to_string(v) + '\n');
        g1.insert({1, v});
        ruszt.insert(v);
        // cerr << "u\n";
    }
    for (auto i : g[v]) {
        if (vis[i])
            continue;
        dfs(i);
    }
}
void dfs2(int v) {
    if (v2[v])
        return;
    v2[v] = 1;
    for (auto i : gg[v]) {
        if (v2[i])
            continue;
        dfs2(i);
    }
    if (g2.find({1, v}) == g2.end() && v != 1)
        ans.pb("- 1 " + to_string(v) + '\n');
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int m1, m2;
    cin >> m1;
    rep(i, m1) {
        int a, b;
        cin >> a >> b;
        if (a > b)
            swap(a, b);
        g[a].pb(b);
        g[b].pb(a);
        if (a == 1)
            ruszt.insert(b);
        g1.insert({a, b});
    }
    // cerr << " r";
    // for (auto i : ruszt)
    //    // cerr << i << ' ';
    // cerr << '\n';
    cin >> m2;
    rep(i, m2) {
        int a, b;
        cin >> a >> b;
        if (a > b)
            swap(a, b);
        g2.insert({a, b});
        gg[a].pb(b);
        gg[b].pb(a);
    }
    ruszt.insert(1);
    dfs(1);
    for (auto [a, b] : g1) {
        if (a == 1)
            continue;
        if (g2.find({a, b}) == g2.end())
            ans.pb("- " + to_string(a) + ' ' + to_string(b) + '\n');
    }
    for (auto i : g2) {
        if (g1.find(i) == g1.end()) {
            ans.pb("+ " + to_string(i.st) + ' ' + to_string(i.nd) + '\n');
        }
    }
    dfs2(1);
    cout << ans.size() << '\n';
    for (auto i : ans)
        cout << i;
}