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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
//Krzysztof Pieprzak
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<long long, long long> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define Size(x) (int)x.size()
#define VAR(v,n) auto v = (n)
#define FOR(i,a,b) for(VAR(i,a); i < (b); ++i)
#define FORE(i,a,b) for(VAR(i,a); i <= (b); ++i)
#define FORREV(i,a,b) for(VAR(i,b); i >= (a); --i)
#define FORSTEP(i,a,b,step) for(VAR(i,a); i < (b); i += (step))
#define FOREACH(i,c) for(auto i : (c))
#define FOREACHS(i,c,n) for(VAR(i,&(c)[0]); i-(c)<(n); ++i)
#define ALL(x) x.begin(),x.end()
#define CLEAR(t) memset(t, 0, sizeof(t))
#define F first
#define S second
#define MP make_pair
#define PUB push_back
#define POB pop_back
#define pieprzu ios_base::sync_with_stdio(0);
#define debug if(0)

const int    INF = 1000000001;
const double EPS = 10e-9;

const int MAXN = 30000;

struct Operation {
    char sign;
    int v1;
    int v2;

    Operation(char sign, int v1, int v2) : sign(sign), v1(v1), v2(v2) {}
};

vi tInit[MAXN + 5];
vi tFinal[MAXN + 5];

bool visited[MAXN + 5];

int n, mInit, mFinal;
int vSpecial = 1;

vi postOrderOnFinalGraph;
bool shouldBeConnectedToVSpecialInFinal[MAXN + 5];

vector<Operation> operations;

void addOperationAddEdge(int v1, int v2) {
    operations.PUB(Operation('+', v1, v2));
}

void addEdge(int v1, int v2) {
    tInit[v1].PUB(v2);
    tInit[v2].PUB(v1);
    addOperationAddEdge(v1, v2);
}

void addOperationRemoveEdge(int v1, int v2) {
    operations.PUB(Operation('-', v1, v2));
}

void printEdges(int v, vi* graph) {
    printf("%d: ", v);
    FOREACH (w, graph[v]) {
        printf("%d ", w);
    }
    printf("\n");
}

void connectAllToVSpecial() {
    sort(ALL(tInit[vSpecial]));

    debug printf("vSpecial start\n");
    debug printEdges(vSpecial, tInit);

    int iInit = 0;
    FORE (v, 1, n) {
        if (v != vSpecial) {
            if (tInit[vSpecial][iInit] != v) {
                debug printf("Adding edge <%d, %d>\n", vSpecial, v);
                addEdge(vSpecial, v);
            } else {
                ++iInit;
            }
        }
    }

    debug printf("vSpecial all\n");
    debug printEdges(vSpecial, tInit);
}

void addAndRemoveEdgesIgnoringVSpecial() {
    FORE (v, 1, n) {
        if (v != vSpecial) {
            sort(ALL(tInit[v]));
            sort(ALL(tFinal[v]));

            debug printf("\n");
            debug printEdges(v, tInit);
            debug printEdges(v, tFinal);

            int nInit = Size(tInit[v]);
            int nFinal = Size(tFinal[v]);
            int jInit = 0;
            int jFinal = 0;
            debug printf("Parameters for next iteration: <%d, %d, %d, %d, %d>\n", v, jInit, nInit, jFinal, nFinal);
            while ((jInit < nInit && tInit[v][jInit] < v) || (jFinal < nFinal && tFinal[v][jFinal] < v)) {
                // edge exists in both init and final graph
                if (jInit < nInit && jFinal < nFinal && tInit[v][jInit] == tFinal[v][jFinal]) {
                    debug printf("Edge <%d, %d> exists in both graphs - skipping\n", v, tInit[v][jInit]);
                    ++jInit;
                    ++jFinal;
                // edge exists only in the init graph - remove edge if it's not connected to specialV
                } else if (jInit < nInit && (jFinal >= nFinal || tInit[v][jInit] < tFinal[v][jFinal])) {
                    debug printf("Edge <%d, %d> exists only in the init graph ", v, tInit[v][jInit]);
                    if (tInit[v][jInit] != vSpecial) {
                        debug printf("- removing\n");
                        addOperationRemoveEdge(v, tInit[v][jInit]);
                    } else {
                        debug printf("but it is connected to vSpecial - skipping\n");
                    }
                    ++jInit;
                // edge exists only in the final graph - add edge
                } else { // jInit == nInit || (jFinal < nFinal && tInit[v][jInit] > tFinal[v][jFinal])
                    debug printf("Edge <%d, %d> exists only in the final graph - adding\n", v, tFinal[v][jFinal]);
                    addOperationAddEdge(v, tFinal[v][jFinal]);
                    ++jFinal;
                }
                debug printf("Parameters for next iteration: <%d, %d, %d, %d, %d>\n", v, jInit, nInit, jFinal, nFinal);
            }
        }
    }
}

void dfsOnFinalGraph(int v) {
    visited[v] = 1;

    FOREACH (w, tFinal[v]) {
        if (!visited[w]) {
            dfsOnFinalGraph(w);
        }
    }

    postOrderOnFinalGraph.PUB(v);
}

void removeRedundantEdgesFromVSpecial() {
    if (Size(tFinal[vSpecial]) == n - 1) {
        debug printf("\nNo need to remove anything connected to vSpecial\n");
        return;
    }

    FOREACH (v, tFinal[vSpecial]) {
        shouldBeConnectedToVSpecialInFinal[v] = 1;
    }

    dfsOnFinalGraph(vSpecial);
    debug {
        printf("\npostOrderOnFinalGraph\n");
        FOREACH (v, postOrderOnFinalGraph) {
            printf("%d ", v);
        }
        printf("\n");
    }

    FOREACH (v, postOrderOnFinalGraph) {
        if (v != vSpecial && !shouldBeConnectedToVSpecialInFinal[v]) {
            debug printf("Removing edge <%d, %d>\n", vSpecial, v);
            addOperationRemoveEdge(vSpecial, v);
        }
    }
}

void rob(int test) {
    scanf("%d", &n);

    int a, b;
    scanf("%d", &mInit);
    FOR (i, 0, mInit) {
        scanf("%d %d", &a, &b);
        tInit[a].PUB(b);
        tInit[b].PUB(a);
    }

    scanf("%d", &mFinal);
    FOR (i, 0, mFinal) {
        scanf("%d %d", &a, &b);
        tFinal[a].PUB(b);
        tFinal[b].PUB(a);
    }

    // at most n operations
    connectAllToVSpecial();

    // at most mFinal added edges and mInit removed edges = at most mInit + mFinal operations
    addAndRemoveEdgesIgnoringVSpecial();

    // at most n operations
    removeRedundantEdgesFromVSpecial();

    // total operations <= n + mInit + mFinal + n = 2 * 30000 + 2 * 50000 = 160000 < 200000
    printf("%d\n", Size(operations));
    FOREACH (operation, operations) {
        printf("%c %d %d\n", operation.sign, operation.v1, operation.v2);
    }
}

int main() {
    int test = 1;
    //scanf("%d", &test);

    FORE (i, 1, test) rob(i);

    return 0;
}