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
#include <cstdio>
#include <unordered_set>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX 55000

struct hashFunction { 
  size_t operator()(const pair<int , int> &x) const {  return (size_t(x.first) << 30) ^ x.second;  } 
}; 

unordered_set<pair<int, int>, hashFunction> E[2];
vector<int> G[2][MAX];
int n,m[2],a,b;
int visited[2][MAX];
vector<int> visitedG[2];

void visit(int v,int K) {
    if (visited[K][v]) return;
    visitedG[K].push_back(v);
    visited[K][v] = 1;
    for(auto w: G[K][v])
        visit(w,K);
}

vector<tuple<char,int,int>> result;

int main() {
    scanf("%d", &n);
    for(int K=0;K<2;K++) {
        scanf("%d", &m[K]);
        for(int i=0;i<m[K];i++) {
            scanf("%d %d", &a, &b);
            if (a>b) swap(a,b);
            E[K].emplace(a,b);
            G[K][a].push_back(b);
            G[K][b].push_back(a);
        }
    }
    visit(1, 0);
    visit(1, 1);
    for(int i = 1;i < visitedG[0].size(); i++) {
        if (!E[0].contains({1,visitedG[0][i]})) result.emplace_back('+', 1, visitedG[0][i]);
    }
    for (auto e: E[0]) {
        if (e.first != 1 && (!E[1].contains(e)))  result.emplace_back('-', e.first, e.second);
    }
    for (auto e: E[1]) {
        if (e.first != 1 && (!E[0].contains(e)))  result.emplace_back('+', e.first, e.second);
    }
    for(int i = visitedG[1].size()-1;i > 0; i--) {
        if (!E[1].contains({1,visitedG[1][i]})) result.emplace_back('-', 1, visitedG[1][i]);
    }
    printf("%ld\n", result.size());
    for(auto r: result) {
        printf("%c %d %d\n", get<0>(r), get<1>(r), get<2>(r));
    }
}