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

struct Graph {
    int n;
    std::vector<std::vector<int>> neighbours;
    std::set<std::pair<int, int>> edges;
    std::vector<std::tuple<char, int, int>> operations;
    Graph(int _n) : n(_n), neighbours(n + 1) { }

    void read() {
        int m;
        std::cin >> m;
        while(m--) {
            int u, v;
            std::cin >> u >> v;
            neighbours[u].push_back(v);
            neighbours[v].push_back(u);
            edges.insert({u, v});
            edges.insert({v, u});
        }
    }

    void add_edge(int u, int v) {
        //assert(std::find(neighbours[u].begin(), neighbours[u].end(), v) == neighbours[u].end());
        //assert(std::find(neighbours[v].begin(), neighbours[v].end(), u) == neighbours[v].end());
        //neighbours[u].insert(v);
        //neighbours[v].insert(u);
        operations.push_back({'+', u, v});
    }

    void remove_edge(int u, int v) {
        //assert(std::find(neighbours[u].begin(), neighbours[u].end(), v) != neighbours[u].end());
        //assert(std::find(neighbours[v].begin(), neighbours[v].end(), u) != neighbours[v].end());
        //neighbours[u].erase(v);
        //neighbours[v].erase(u);
        operations.push_back({'-', u, v});
    }

    void dfs(int x, std::vector<bool>& processed) {
        processed[x] = true;
        if(x != 1 and edges.find({1, x}) == edges.end()) {
            add_edge(1, x);
        }

        for(int neighbour : neighbours[x]) {
            if(processed[neighbour])
                continue;
            dfs(neighbour, processed);
        }
    }

    void turn_into_1star() {
        // first add edges (1, x) for all x
        std::vector<bool> processed(n + 1, false);
        dfs(1, processed);
        // then erase all unwanted edges
        for(auto edge : edges) {
            if(edge.first < edge.second and edge.first != 1) {
                remove_edge(edge.first, edge.second);
            }
        }
    }

    void print() {
        for(auto t : operations) {
            std::cout << std::get<0>(t) << " " << std::get<1>(t) << " " << std::get<2>(t) << "\n";
        }
    }

    void print_in_reverse() {
        for(auto ptr = operations.rbegin(); ptr != operations.rend(); ptr++) {
            auto t = *ptr;
            std::cout << (std::get<0>(t)=='-' ? '+' : '-') << " " << std::get<1>(t) << " " << std::get<2>(t) << "\n";
        }
    }
};

int main() {
    int n;
    std::cin >> n;
    Graph G_startowy(n), G_docelowy(n);
    G_startowy.read();
    G_docelowy.read();
    G_startowy.turn_into_1star();
    G_docelowy.turn_into_1star();

    std::cout << (G_startowy.operations.size() + G_docelowy.operations.size()) << "\n";
    G_startowy.print();
    G_docelowy.print_in_reverse();
}