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
#include <bits/stdc++.h>

using namespace std;

const int N = 30 * 1000 + 2;

vector<int> graphs[2][N];
map<pair<int,int>, int> edges[2];
int visited[2][N];
int m[2];

vector<pair<char, pair<int,int>>> mods;

void get_graph(int n, int r) {
    cin >> m[r];
    int u, v;
    for (int i = 0; i < m[r]; i++) {
        cin >> u >> v;
        edges[r][{u, v}] = 1;
        edges[r][{v, u}] = 1;
        graphs[r][u].push_back(v);
        graphs[r][v].push_back(u);
    }
}

void dfs1(int v, int root, int r) {
    visited[r][v] = 1;
    for (auto u : graphs[r][v]) {
        if (visited[r][u] == 0) {
            if (edges[0][{root,u}] == 0)
                mods.push_back({'+', {root, u}});
            dfs1(u, root, r); 
        }
    }
}


void fix_edges_one_left(int v) {
    for (int i = 0; i < N; i++) {
        for (auto u : graphs[0][i]) {
            if (u != v && i != v) {
                if (edges[1][{i, u}] == 0 && edges[0][{i, u}] == 1) {
                    //cout << "-" << i << " " << u;
                    mods.push_back({'-', {i, u}});
                    edges[0][{i, u}] = 0;
                    edges[0][{u, i}] = 0;
                }
            }
        }
    }
    for (int i = 0; i < N; i++) {
        for (auto u : graphs[1][i]) {
            if (u != v && i != v) {
                if (edges[0][{i, u}] == 0) {
                    //cout << "+" << i << " " << u;
                    mods.push_back({'+', {i, u}});
                    edges[0][{i, u}] = 1;
                    edges[0][{u, i}] = 1;
                }
            }
        }
    }
}

void dfs2(int v, int root, int r) {
    visited[r][v] = 1;
    for (auto u : graphs[r][v]) {
        if (visited[r][u] == 0) {
            dfs2(u, root, r); 
        }
    }
    if (edges[1][{root, v}] == 0 && root != v) {
        //cout << "-" << root << " " v << "\n";
        mods.push_back({'-', {root, v}});
    }
}

int main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);    
    
    int n;
    cin >> n;
    get_graph(n, 0);
    get_graph(n, 1);
    int v1 = 1;
    dfs1(v1, v1, 0);
    fix_edges_one_left(v1);
    dfs2(v1, v1, 1);
    cout << mods.size() << "\n";
    for (auto mod : mods)
        cout << mod.first << " " << mod.second.first << " " << mod.second.second << "\n";
    return 0;
}