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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<bits/stdc++.h>

using namespace std;

int n,mo,mn;

bool one_old[30010];
bool one_new[30010];
vector<int> gold[30010];
vector<int> gnew[30010];

vector<pair<int,int>> eadd;
vector<pair<int,int>> edel;
vector<pair<int,int>> redel;

void update(int idx){
    int ptr1 = 0,ptr2 = 0;
    if(gold[idx][ptr1] == 1){
        ptr1++;
    }
    if(gnew[idx][ptr2] == 1){
        ptr2++;
    }
    while(ptr1 < (int)gold[idx].size() && ptr2 < (int)gnew[idx].size()){        
        if(gold[idx][ptr1] < gnew[idx][ptr2]){
            if(idx < gold[idx][ptr1])
                edel.push_back({idx,gold[idx][ptr1]});
            ptr1++;
            continue;
        }
        if(gold[idx][ptr1] > gnew[idx][ptr2]){
            if(idx < gnew[idx][ptr2])
                eadd.push_back({idx,gnew[idx][ptr2]});
            ptr2++;
            continue;
        }
        ptr1++;
        ptr2++;
    }
    while(ptr1 < (int)gold[idx].size()){
        if(idx < gold[idx][ptr1])
            edel.push_back({idx,gold[idx][ptr1]});
        ptr1++;
    }
    while(ptr2 < (int)gnew[idx].size()){
        if(idx < gnew[idx][ptr2])
            eadd.push_back({idx,gnew[idx][ptr2]});
        ptr2++;
    }
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    cin >> n;
    cin >> mo;
    int a,b;
    for(int i = 0; i < mo; i++){
        cin >> a >> b;
        if(a == 1) one_old[b] = true;
        if(b == 1) one_old[a] = true;
        gold[a].push_back(b);
        gold[b].push_back(a);
    }
    cin >> mn;
    for(int i = 0; i < mn; i++){
        cin >> a >> b;
        if(a == 1) one_new[b] = true;
        if(b == 1) one_new[a] = true;
        gnew[a].push_back(b);
        gnew[b].push_back(a);
    }

    for(int i = 1; i <= n; i++){
        sort(gold[i].begin(),gold[i].end());
        sort(gnew[i].begin(),gnew[i].end());
    }

    queue<int> que;
    for(auto i : gold[1]){
        que.push(i);
    }

    while(!que.empty()){
        a = que.front();
        que.pop();
        for(auto i : gold[a]){
            if(i == 1) continue;
            if(!one_old[i]){
                one_old[i] = true;
                eadd.push_back({1,i});
                // cout << "+ " << 1 << " " << i << "\n";
                que.push(i);
            }
        }
    }

    for(int i = 2 ; i <= n; i++){
        update(i);
    }

    for(auto i : gnew[1]){
        que.push(i);
    }

    while(!que.empty()){
        a = que.front();
        que.pop();
        for(auto i : gnew[a]){
            if(i == 1) continue;
            if(!one_new[i]){
                one_new[i] = true;
                redel.push_back({1,i});
                // cout << "+ " << 1 << " " << i << "\n";
                que.push(i);
            }
        }
    }

    cout << eadd.size() + edel.size() + redel.size() << "\n";
    for(pair<int,int> i : eadd){
        cout << "+ " << i.first << " " << i.second << "\n";
    }
    for(pair<int,int> i : edel){
        cout << "- " << i.first << " " << i.second << "\n";
    }
    reverse(redel.begin(),redel.end());
    for(pair<int,int> i : redel){
        cout << "- " << i.first << " " << i.second << "\n";
    }
    return 0;
}
/*
7
6
1 5
1 2
1 4
7 1
1 3
1 6
6
1 5
5 4
4 6
6 3
3 7
7 2
*/