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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include<vector>
#include <stack>
#include <algorithm>
#include <string>

using namespace std;

std::vector<int> dfs(int x, std::vector< std::vector<int>> &v,
                     std::vector<int> &visited1){
    std::vector<int> route1;
    std::stack<int> s;
    s.push(x);
    while(!s.empty()) {
        x = s.top();
        s.pop();

        if (visited1[x] == 0) {
            route1.push_back(x);
            visited1[x] = 1;

            for (int i : v[x]){
                if (visited1[i] == 0){
                    s.push(i);
                }
            }
        }
    }
    return route1;
}

int main(){
    ios_base::sync_with_stdio(0);
    int n, m1, m2, a, b;

    cin >> n;
    cin >> m1;

    std::vector< std::vector<int>> v1(n + 1);
    std::vector< std::vector<int>> v2(n + 1);
    for (int i = 0; i < m1; i++){
        cin >> a >> b;
        v1[a].push_back(b);
        v1[b].push_back(a);
    }

    cin >> m2;
    for (int i = 0; i < m2; i++){
        cin >> a >> b;
        v2[a].push_back(b);
        v2[b].push_back(a);
    }

    std::vector<int> visited1(n + 1, 0);
    auto route1 = dfs(1, v1, visited1);

    std::vector<int> edges_with_first(n + 1, 0);
    for (int i : v1[1]) {

        edges_with_first[i] = 1;
    }
    std::vector<string> moves;
    moves.reserve(3 * n);

    for (int i = 1; i < n; i++){
        int elem = route1[i];
        if (edges_with_first[elem] == 0) {
            moves.push_back("+ 1 " + to_string(elem));
//            cout << "+ 1 " << elem << endl;
        }
    }

    for (int i = 2; i <= n; i++){
        for (int elem : v1[i]){
            if (elem != 1 && elem > i){
                moves.push_back("- " + to_string(i) + " " + to_string(elem));
//                cout << "- " << i << " " << elem << endl;
            }
        }
    }

    for (int i = 2; i <= n; i++){
        for (int elem : v2[i]){
            if (elem != 1 && elem > i){
                moves.push_back("+ " + to_string(i) + " " + to_string(elem));
//                cout << "+ " << i << " " << elem << endl;
            }
        }
    }

    std::vector<int> visited2(n + 1, 0);
    auto route2 = dfs(1, v2, visited2);

    edges_with_first = std::vector<int>(n + 1, 0);
    for (int i : v2[1]) {
        edges_with_first[i] = 1;
    }
    for (int i = n - 1; i > 0; i--){
        int elem = route2[i];
        if (edges_with_first[elem] == 0) {
            moves.push_back("- 1 " + to_string(elem));
//            cout << "- 1 " << elem << endl;
        }
    }

    cout << moves.size() << endl;
    for (const auto& line : moves){
        cout << line << endl;
    }


    return 0;
}