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

#define st first
#define nd second
#define shandom_ruffle random_shuffle

const int MAXN = 30005;

vector<vector<int>> g1, g2;
set<pair<int, int>> e1, e2;
vector<int> vis;

int n;

void scan_graph(vector<vector<int>> &g, set<pair<int, int>> &e) {
    int m;
    scanf("%d", &m);
    
    for (int i=0; i<m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        
        g[a].push_back(b);
        g[b].push_back(a);
        
        e.insert({min(a, b), max(a, b)});
    }
}

vector<pair<int, int>> links, unlinks;

void link_op(int a, int b) {
    links.push_back({min(a, b), max(a, b)});
}

void make_tree(const vector<vector<int>> &g, int x) {
    bool has_link = (x == 1);
    vis[x] = 1;
    
    for (int a : g[x]) {
        if (a == 1)
            has_link = true;
    }
    
    if (!has_link)
        link_op(x, 1);
    
    for (int a : g[x]) {
        if (vis[a])
            continue;
        
        make_tree(g, a);
    }
}

void add_edges(set<pair<int, int>> &my_e, set<pair<int, int>> &opp_e) {
    for (auto &next : opp_e) {
        if (my_e.find(next) != my_e.end())
            continue;
        
        if (next.st == 1 || next.nd == 1)
            continue;
        
        link_op(next.st, next.nd);
    }
}

int main() {
    scanf("%d", &n);
    g1.resize(n+5);
    g2.resize(n+5);
    
    scan_graph(g1, e1);
    scan_graph(g2, e2);
    
    vis.resize(n+5);
    make_tree(g1, 1);
    
    add_edges(e1, e2);
    
    // reverse the ops
    links.swap(unlinks);
    
    vis.clear();
    vis.resize(n+5);
    make_tree(g2, 1);
    
    add_edges(e2, e1);
    
    links.swap(unlinks);
    
    printf("%d\n", (int)(links.size() + unlinks.size()));
    
    for (auto p : links)
        printf("+ %d %d\n", p.st, p.nd);
    
    for (int i=unlinks.size()-1; i>=0; i--) {
        printf("- %d %d\n", unlinks[i].st, unlinks[i].nd);
    }
    
    return 0;
}