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

struct Move{
    bool sign;
    int first, second;
};

const int N = 30'003;
bitset<N> neighbours, visited;
vector<int> G[N];
vector<Move> ans;
vector<pair<int, int>> goal, start;
int r = 0;

void dfs(int v){
    visited[v] = true;
    if(!neighbours[v]){
        ans.push_back({true, 1, v});
        r++;
    }
    for(int u : G[v]){
        if(!visited[u]) dfs(u);
    }
}

int main(){
    int n, m1, m2, v, u;
    scanf("%d\n%d", &n, &m1);
    neighbours[1] = true;
    for(int i = 0 ; i < m1 ; i++){
        scanf("%d %d", &v, &u);
        G[u].push_back(v);
        G[v].push_back(u);
        start.push_back({v, u});
        if(v == 1 || u == 1) neighbours[max(u, v)] = true;
    }
    scanf("%d", &m2);
    for(int i = 0 ; i < m2 ; i++){
        scanf("%d %d", &v, &u);
        goal.push_back({v, u});
    }
    dfs(1);
    for(int i = 0 ; i < m1 ; i++){
        v = start[i].first;
        u = start[i].second;
        if(v != 1 && u != 1){
            ans.push_back({false, u, v});
            r++;
        }
    }
    neighbours.reset();
    for(int i = 0 ; i < m2 ; i++){
        v = goal[i].first;
        u = goal[i].second;
        if(v != 1 && u != 1){
            ans.push_back({true, u, v});
            r++;
        }
        if(v == 1 || u == 1) neighbours[max(u, v)] = true;
    }
    for(int i = 2 ; i <= n ; i++){
        if(!neighbours[i]){
            r++;
            ans.push_back({false, 1, i});
        }
    }
    printf("%d\n", r);
    for(Move x : ans){
        if(x.sign) printf("+ %d %d\n", x.first, x.second);
        else printf("- %d %d\n", x.first, x.second);
    }
}