QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#125229#6745. Delete the Treehos_lyricAC ✓1ms3800kbC++144.2kb2023-07-16 07:54:142023-07-16 07:54:18

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-16 07:54:18]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3800kb
  • [2023-07-16 07:54:14]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


int N;
vector<int> A, B;

vector<int> ds;

vector<vector<int>> G;
vector<int> sz, del;
void dfsSz(int u, int p) {
  sz[u] = 1;
  for (const int i : G[u]) {
    const int v = A[i] ^ B[i] ^ u;
    if (v != p) {
      dfsSz(v, u);
      sz[u] += sz[v];
    }
  }
}
string dfsString(int u, int p) {
  ostringstream oss;
  oss << "[" << u;
  for (const int i : G[u]) {
    const int v = A[i] ^ B[i] ^ u;
    if (!del[v] && v != p) {
      oss << " " << dfsString(v, u);
    }
  }
  oss << "]";
  return oss.str();
}
/// vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
void dfs(int j, int u, int p, int d) {
  for (const int i : G[u]) {
    const int v = A[i] ^ B[i] ^ u;
    if (!del[v] && v != p) {
      dfs(j, v, u, d + 1);
    }
  }
}
/// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
void solveSubtree(int depth, int r) {
#ifdef LOCAL
  cerr << string(2 * depth, ' ') << "solveSubtree " << dfsString(r, -1) << endl;
#endif
  vector<int> is, vs;
  for (const int i : G[r]) {
    const int v = A[i] ^ B[i] ^ r;
    if (!del[v]) {
      is.push_back(i);
      vs.push_back(v);
    }
  }
  const int len = vs.size();
  /// vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
  ds[r] = depth;
  /*
  for (int j = 0; j < len; ++j) {
    const int i = is[j], v = vs[j];
    dfs(j, v, r, 1);
  }
  */
  /// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
}
void solveRec(int depth, int u) {
  for (; ; ) {
    int vm = -1;
    for (const int i : G[u]) {
      const int v = A[i] ^ B[i] ^ u;
      if (!del[v]) {
        if (!~vm || sz[vm] < sz[v]) {
          vm = v;
        }
      }
    }
    if (!~vm || 2 * sz[vm] <= sz[u]) {
      solveSubtree(depth, u);
      del[u] = 1;
      for (const int i : G[u]) {
        const int v = A[i] ^ B[i] ^ u;
        if (!del[v]) {
          solveRec(depth + 1, v);
        }
      }
      break;
    } else {
      sz[u] -= sz[vm];
      sz[vm] += sz[u];
      u = vm;
    }
  }
}
void centroidDecomp() {
  sz.assign(N, 0);
  dfsSz(0, -1);
  del.assign(N, 0);
  solveRec(0, 0);
}


int main() {
  for (; ~scanf("%d", &N); ) {
    A.resize(N - 1);
    B.resize(N - 1);
    for (int i = 0; i < N - 1; ++i) {
      scanf("%d%d", &A[i], &B[i]);
      --A[i];
      --B[i];
    }
    
    G.assign(N, {});
    for (int i = 0; i < N - 1; ++i) {
      G[A[i]].push_back(i);
      G[B[i]].push_back(i);
    }
    ds.assign(N, -1);
    centroidDecomp();
// cerr<<"ds = "<<ds<<endl;
    
    int len = 0;
    for (int u = 0; u < N; ++u) {
      chmax(len, ds[u]);
    }
    ++len;
    
    vector<vector<int>> uss(len);
    for (int u = 0; u < N; ++u) {
      uss[ds[u]].push_back(u);
    }
    
    printf("%d\n", len);
    for (int d = len; --d >= 0; ) {
      printf("%d", (int)uss[d].size());
      for (const int u : uss[d]) {
        printf(" %d", u + 1);
      }
      puts("");
    }
  }
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3664kb

input:

5
1 2
1 3
1 4
4 5

output:

3
1 5
3 2 3 4
1 1

result:

ok 

Test #2:

score: 0
Accepted
time: 1ms
memory: 3628kb

input:

500
183 443
32 443
334 443
254 443
331 443
348 443
54 443
430 443
275 443
410 443
360 443
443 468
140 443
179 443
93 443
327 443
128 443
365 443
122 443
43 443
46 443
399 443
398 443
269 443
130 443
227 443
412 443
61 443
295 443
98 443
30 443
197 443
397 443
95 443
192 443
266 443
48 443
310 443
28...

output:

2
499 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 10...

result:

ok 

Test #3:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

500
80 180
80 254
1 180
80 337
180 323
80 248
180 205
80 189
180 480
80 330
180 454
80 498
142 180
80 193
180 346
80 89
180 389
80 125
180 232
80 93
180 228
80 327
180 357
80 417
180 362
80 278
180 316
80 312
163 180
80 310
176 180
80 463
180 210
80 478
180 294
80 185
124 180
80 143
180 339
80 253
1...

output:

3
249 3 5 7 8 10 15 18 20 21 23 27 28 32 33 34 35 43 46 48 50 51 53 54 55 56 61 62 63 64 65 68 72 76 77 78 79 83 86 87 88 89 91 93 94 95 96 98 106 109 111 114 118 120 123 125 126 127 128 130 131 135 137 138 139 143 144 146 147 149 150 151 152 154 156 158 159 161 162 164 165 167 168 171 172 174 177 1...

result:

ok 

Test #4:

score: 0
Accepted
time: 1ms
memory: 3740kb

input:

500
387 488
301 488
301 413
13 413
13 265
176 265
176 398
74 398
74 241
241 415
386 415
386 448
210 448
210 285
147 285
147 264
19 264
19 314
314 335
54 335
54 261
261 484
425 484
350 425
156 350
156 164
164 420
8 420
8 309
230 309
230 441
408 441
183 408
183 410
204 410
204 318
151 318
151 328
328 ...

output:

9
245 4 5 6 7 8 10 11 13 14 16 20 22 24 25 27 28 29 31 32 37 38 39 44 50 51 54 55 57 61 62 63 64 65 70 74 77 79 80 81 82 83 86 92 94 95 97 98 102 103 105 106 110 112 113 114 115 116 119 122 123 124 127 129 131 132 135 137 140 143 144 148 149 152 155 157 158 160 161 164 165 167 168 170 173 175 176 17...

result:

ok 

Test #5:

score: 0
Accepted
time: 1ms
memory: 3692kb

input:

500
147 209
104 147
13 209
209 466
104 485
17 104
13 214
13 179
151 466
176 466
130 485
286 485
17 359
17 178
214 486
55 214
179 350
179 327
151 167
151 498
146 176
102 176
99 130
130 232
286 294
286 389
56 359
330 359
178 488
178 441
440 486
210 486
55 157
55 458
237 350
350 352
327 371
317 327
167...

output:

9
1 85
252 3 5 6 7 9 10 18 19 20 22 24 25 27 29 31 32 33 34 35 37 38 39 41 44 47 48 49 51 53 57 58 59 60 61 62 63 64 66 67 70 71 73 81 86 87 90 91 94 95 96 100 107 112 113 116 120 123 128 129 132 133 138 139 140 141 142 143 147 149 153 155 156 158 160 161 163 164 166 168 169 170 173 174 180 181 182 ...

result:

ok 

Test #6:

score: 0
Accepted
time: 1ms
memory: 3696kb

input:

500
323 449
449 474
198 449
431 449
69 449
336 449
402 449
240 449
43 449
82 449
335 449
86 449
427 449
220 449
26 449
449 477
449 465
73 449
325 449
1 449
144 449
432 449
203 449
443 449
95 323
323 437
323 337
152 323
185 323
323 484
165 323
41 323
322 323
323 334
32 323
118 323
232 323
57 323
323 ...

output:

3
475 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 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 70 71 72 74 75 76 77 78 79 80 81 83 84 85 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 10...

result:

ok 

Test #7:

score: 0
Accepted
time: 1ms
memory: 3736kb

input:

500
274 432
133 274
274 491
274 455
207 274
274 315
265 274
10 274
203 274
274 289
274 474
374 432
414 432
116 274
385 414
274 364
1 491
10 365
432 493
10 306
374 463
5 116
302 385
265 285
127 315
86 127
127 246
282 374
98 302
98 206
282 344
127 391
127 231
62 231
33 231
86 104
211 365
194 206
194 4...

output:

9
14 8 27 64 81 150 167 180 206 276 311 344 414 430 466
92 2 13 21 32 37 38 41 42 44 45 47 53 66 67 77 79 83 94 98 100 112 121 126 138 147 151 152 166 173 192 193 195 205 223 225 252 253 260 261 267 268 278 282 284 286 288 296 305 308 316 317 318 319 322 325 332 338 352 359 366 369 372 383 385 386 3...

result:

ok 

Test #8:

score: 0
Accepted
time: 1ms
memory: 3684kb

input:

500
50 287
287 496
64 287
287 454
149 287
63 287
287 372
108 287
52 287
287 320
287 406
155 287
287 294
128 287
17 287
259 287
6 287
54 294
128 462
247 287
161 287
128 440
172 287
171 287
156 287
397 496
108 270
350 397
287 432
7 259
54 183
280 320
473 496
50 88
432 494
54 195
79 287
50 94
41 320
70...

output:

8
41 12 27 38 40 47 57 76 84 89 106 131 142 143 145 162 199 201 206 213 251 255 261 264 272 274 295 296 305 327 332 335 338 347 356 370 417 418 419 424 431 481
105 3 23 29 30 34 35 36 49 51 56 58 61 65 67 74 82 86 87 92 110 112 113 116 120 137 138 139 148 150 152 157 158 163 166 169 174 185 189 209 ...

result:

ok 

Test #9:

score: 0
Accepted
time: 0ms
memory: 3716kb

input:

500
93 209
209 367
209 438
209 314
209 332
152 209
209 443
209 471
209 315
209 342
209 459
209 460
209 462
209 211
209 341
191 209
209 329
185 209
209 350
209 468
209 493
209 363
209 224
35 209
209 253
209 212
86 209
204 209
186 209
209 262
193 209
209 275
209 427
141 209
88 209
149 209
209 409
209 ...

output:

9
48 3 6 9 16 23 53 83 95 104 113 123 161 168 174 176 177 181 200 218 234 244 252 260 266 277 291 296 304 319 321 323 336 373 374 375 377 378 381 390 392 396 397 433 434 439 441 452 474
128 4 5 7 8 11 12 17 19 20 21 22 25 26 27 34 40 41 43 45 52 57 60 65 70 71 75 77 79 80 81 87 94 100 102 111 112 11...

result:

ok 

Test #10:

score: 0
Accepted
time: 1ms
memory: 3688kb

input:

500
130 139
139 400
130 318
267 318
318 389
21 400
21 36
21 26
267 321
321 401
18 321
200 389
200 307
66 200
36 274
95 274
96 274
26 357
192 357
220 357
385 401
290 385
46 385
18 53
53 301
53 231
166 307
166 287
3 166
66 212
212 410
212 438
95 155
151 155
155 305
41 96
41 478
41 148
112 192
112 137
...

output:

8
192 2 4 6 8 10 13 14 16 22 25 28 32 35 38 42 44 45 48 50 55 56 60 61 65 67 68 76 78 80 82 90 91 93 94 99 100 103 104 108 109 110 113 115 117 118 121 122 123 127 128 134 136 138 141 142 143 149 152 153 154 156 159 161 162 163 164 165 168 169 170 173 174 178 179 182 189 198 201 202 204 205 206 207 2...

result:

ok 

Test #11:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

500
117 264
117 456
175 264
264 500
2 456
218 456
175 480
175 343
265 500
432 500
2 475
2 487
63 218
218 421
377 480
444 480
84 343
151 343
265 281
133 265
252 432
181 432
346 475
445 475
16 487
330 487
25 63
63 102
79 421
101 421
266 377
142 377
409 444
434 444
84 291
84 284
8 151
151 333
281 358
2...

output:

9
119 4 10 13 14 15 20 21 33 35 37 38 43 48 62 73 78 80 85 87 92 96 97 106 109 113 116 117 120 128 131 144 145 147 148 157 158 160 174 176 177 185 188 194 195 198 200 202 207 216 224 230 237 240 244 249 255 268 270 272 277 279 287 288 289 295 296 299 300 306 308 312 319 323 328 334 342 344 345 351 3...

result:

ok 

Test #12:

score: 0
Accepted
time: 1ms
memory: 3684kb

input:

500
33 453
291 377
33 291
73 424
215 392
66 496
66 215
309 424
66 309
246 291
246 309
154 467
454 482
110 184
110 454
154 455
110 455
56 199
155 494
56 155
294 311
102 109
105 225
105 109
289 311
105 289
155 452
289 452
347 455
347 452
113 246
113 347
43 463
232 292
83 386
83 232
299 463
83 299
293 ...

output:

8
52 5 6 18 37 57 73 78 85 93 98 101 102 120 130 140 142 148 163 173 174 199 219 238 245 254 259 292 297 303 309 325 331 334 338 344 348 352 354 355 359 363 368 392 408 409 423 439 453 458 472 484 492
184 1 2 7 16 20 21 22 24 25 33 40 43 45 46 47 49 52 54 56 61 62 64 65 70 72 74 75 79 81 82 84 88 90...

result:

ok 

Test #13:

score: 0
Accepted
time: 1ms
memory: 3756kb

input:

500
206 498
238 388
130 427
130 388
473 498
130 473
343 352
362 421
343 421
76 170
3 180
162 460
162 180
1 76
1 162
193 421
1 193
350 473
193 350
223 488
24 30
30 223
82 300
303 468
59 125
59 468
68 82
59 68
30 107
68 107
334 406
153 278
217 372
153 217
111 334
111 217
41 190
63 288
190 288
48 230
1...

output:

8
12 9 32 195 238 278 332 376 397 430 432 441 481
120 1 3 10 20 26 28 34 39 41 46 48 50 52 60 61 67 71 73 74 79 84 87 90 94 95 97 108 110 120 129 136 146 147 148 150 153 154 155 166 170 175 181 182 184 186 189 191 200 202 206 222 225 228 229 232 234 240 244 246 248 253 256 257 259 260 262 263 264 27...

result:

ok 

Test #14:

score: 0
Accepted
time: 1ms
memory: 3708kb

input:

500
27 364
192 250
277 488
250 277
27 78
78 277
309 500
361 376
376 500
311 491
270 273
289 496
270 496
311 418
418 496
107 376
107 418
78 187
107 187
146 320
92 241
241 320
137 450
357 478
37 435
357 435
137 247
247 435
241 443
247 443
382 387
75 398
116 465
75 116
152 387
116 152
50 437
22 456
50 ...

output:

8
30 39 48 61 68 72 87 127 139 154 192 203 213 219 232 237 240 274 280 295 304 321 338 349 385 392 398 431 448 452 486
132 4 5 9 20 41 42 43 47 51 56 57 58 59 62 66 69 75 77 82 84 102 103 113 118 125 128 133 140 146 148 149 159 162 163 164 166 170 184 185 187 195 211 214 216 218 224 226 230 235 239 ...

result:

ok 

Test #15:

score: 0
Accepted
time: 1ms
memory: 3700kb

input:

500
224 468
4 105
342 365
105 365
133 224
133 365
293 476
176 389
389 476
162 227
41 411
453 489
411 453
36 162
36 453
297 389
36 297
133 485
297 485
23 486
95 136
136 486
158 314
10 65
302 491
65 491
314 495
491 495
54 136
54 495
169 488
91 483
40 68
40 483
214 488
40 214
186 375
372 465
186 465
59...

output:

8
91 4 6 9 12 15 17 20 22 25 32 33 39 44 55 63 69 73 81 83 86 87 88 91 98 110 111 115 118 121 123 128 131 138 146 151 157 165 166 172 179 185 191 192 198 199 223 229 230 231 237 244 248 250 251 252 253 259 260 261 263 267 268 274 278 286 298 310 322 329 335 341 354 364 371 377 393 408 424 428 433 43...

result:

ok 

Test #16:

score: 0
Accepted
time: 1ms
memory: 3700kb

input:

500
289 469
30 302
94 224
94 302
175 469
94 175
363 495
38 385
385 495
211 433
106 239
202 268
106 202
32 433
32 202
114 385
32 114
175 455
114 455
92 216
14 459
216 459
262 299
63 321
116 228
63 116
111 299
111 116
324 459
111 324
122 165
269 274
15 193
15 269
144 165
15 144
65 360
77 240
240 360
2...

output:

8
19 25 26 30 37 49 133 191 204 215 245 274 314 349 406 421 426 450 451 460
152 1 3 4 5 6 11 19 20 21 23 32 33 43 48 51 53 58 59 61 62 64 65 66 68 70 82 83 87 90 92 93 95 96 102 103 104 105 107 109 110 113 117 120 122 125 135 136 140 149 150 159 164 167 169 173 186 190 192 193 195 196 206 207 211 21...

result:

ok 

Test #17:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

500
139 315
285 315
263 285
263 329
329 335
132 335
132 288
231 288
231 391
266 391
266 430
410 430
307 410
307 379
117 379
117 121
121 441
370 441
188 370
157 188
157 200
200 486
73 486
73 267
267 404
32 404
32 260
260 286
286 296
296 499
350 499
173 350
152 173
152 458
378 458
114 378
114 172
172 ...

output:

9
48 23 45 52 55 58 70 77 109 113 132 139 147 152 164 172 186 188 225 230 231 235 248 258 259 265 267 268 274 285 286 293 306 307 329 333 341 345 354 357 375 380 383 408 430 441 446 486 500
87 2 7 11 15 28 33 41 47 51 61 67 72 80 86 97 111 114 118 127 134 137 141 143 145 150 159 163 171 181 182 184 ...

result:

ok 

Test #18:

score: 0
Accepted
time: 1ms
memory: 3700kb

input:

500
315 328
140 315
140 285
2 285
2 455
381 455
381 391
244 391
172 244
101 172
101 479
7 479
7 456
456 478
372 478
300 372
300 471
321 471
321 413
182 413
182 209
93 209
93 359
6 359
6 500
418 500
276 418
251 276
251 291
291 388
388 400
288 400
277 288
123 277
81 123
81 165
164 165
99 164
99 406
15...

output:

9
147 1 2 3 5 6 12 15 16 19 23 24 26 31 33 36 38 39 46 53 54 58 60 67 69 70 71 72 73 80 86 91 93 96 97 104 113 114 116 118 120 126 128 129 133 140 143 153 155 158 164 166 173 179 185 186 187 192 207 208 213 217 227 233 238 239 240 243 244 247 248 249 250 251 252 259 261 264 266 269 277 286 289 292 2...

result:

ok 

Test #19:

score: 0
Accepted
time: 1ms
memory: 3704kb

input:

500
87 420
87 165
165 457
85 457
85 187
187 435
56 435
56 409
268 409
153 268
40 153
40 225
225 451
68 451
68 362
88 362
88 190
190 397
122 397
122 264
202 264
75 202
304 420
304 319
200 319
200 258
258 318
24 318
24 138
78 138
78 357
209 357
209 497
58 497
16 58
16 196
196 488
124 488
124 155
155 4...

output:

6
169 1 4 6 11 15 16 19 25 27 28 31 33 35 36 41 44 45 49 53 55 59 60 70 74 75 79 84 86 87 88 90 91 93 103 104 110 112 120 121 125 126 128 129 130 132 135 138 139 140 145 149 153 154 155 157 158 161 163 166 167 168 172 173 174 177 178 181 184 185 187 192 198 201 205 206 208 210 212 213 218 219 222 22...

result:

ok 

Test #20:

score: 0
Accepted
time: 1ms
memory: 3748kb

input:

500
294 400
232 294
294 420
66 294
294 320
294 468
24 294
119 294
294 368
294 442
68 294
262 294
229 294
294 318
50 294
294 463
122 294
53 294
92 294
294 348
180 294
294 496
353 496
488 496
45 496
46 496
35 496
308 496
219 496
377 496
277 496
15 496
16 496
381 496
217 496
372 496
302 496
31 496
117 ...

output:

6
148 2 9 13 14 24 25 28 29 33 48 50 52 53 54 55 56 57 59 60 61 63 65 66 68 72 73 79 86 88 90 92 93 94 96 107 108 110 118 119 121 122 124 129 130 131 132 133 136 150 151 152 162 171 178 180 187 188 190 204 206 208 218 223 229 230 232 237 239 240 246 247 250 257 258 262 273 275 280 283 287 290 291 30...

result:

ok 

Test #21:

score: 0
Accepted
time: 1ms
memory: 3696kb

input:

500
145 194
145 452
145 474
145 413
149 452
194 221
145 438
193 452
221 268
85 145
145 456
145 403
432 456
438 478
298 474
115 298
149 326
79 194
112 145
156 403
403 422
115 347
221 388
145 401
435 478
67 298
39 156
39 253
433 435
115 324
85 256
309 433
281 401
193 445
67 494
1 324
324 473
132 145
1...

output:

8
3 56 247 412
24 18 23 50 57 77 88 90 119 123 124 125 167 172 177 191 203 235 242 305 317 358 379 418 474
85 15 30 36 38 43 44 45 49 65 67 84 91 92 104 106 108 111 126 128 137 141 142 159 164 166 174 175 178 183 189 192 200 201 204 208 220 231 243 245 249 250 257 264 265 269 290 299 304 306 312 313...

result:

ok 

Test #22:

score: 0
Accepted
time: 1ms
memory: 3736kb

input:

500
206 289
289 478
239 289
212 289
212 326
173 206
262 289
24 262
239 250
289 456
326 465
35 478
465 491
215 289
124 215
215 288
8 288
157 289
289 342
116 326
326 453
206 422
236 465
116 292
325 465
2 124
326 448
188 448
132 326
69 478
133 239
8 42
24 127
28 116
135 342
262 473
115 325
126 206
268 ...

output:

8
3 171 337 401
49 1 19 27 33 39 57 58 65 79 94 125 147 151 176 198 225 227 252 254 257 266 270 272 274 278 280 282 305 311 314 331 336 358 359 366 380 381 390 398 400 412 416 417 430 469 472 474 475 490
108 3 7 10 21 22 34 36 38 44 47 51 52 53 67 71 76 83 85 88 89 97 98 104 105 108 114 123 124 133 ...

result:

ok 

Test #23:

score: 0
Accepted
time: 0ms
memory: 3748kb

input:

500
11 250
11 273
11 192
192 360
192 426
34 426
204 426
161 204
204 413
24 413
359 413
290 359
359 386
335 386
386 422
101 422
108 422
108 171
108 183
183 304
183 313
313 497
119 313
119 202
119 370
311 370
306 370
260 306
61 306
61 439
61 110
110 367
110 256
237 256
159 256
159 208
62 159
62 177
62...

output:

9
122 2 4 5 15 20 32 37 39 40 43 46 51 54 58 63 68 71 80 84 85 97 100 101 105 112 118 120 125 126 133 134 136 139 142 145 155 156 161 174 176 190 194 197 199 202 208 209 213 214 217 224 225 233 234 235 239 242 252 253 255 259 260 268 269 270 271 276 283 285 289 290 295 301 304 305 307 314 316 317 32...

result:

ok 

Test #24:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

500
365 463
365 477
324 477
310 477
106 477
106 232
41 106
106 125
125 464
125 293
125 467
467 478
190 467
6 467
6 141
6 453
6 435
412 435
435 444
435 484
476 484
77 484
421 484
156 421
360 421
182 421
182 273
182 471
182 315
115 315
56 315
179 315
179 320
179 328
179 499
242 499
390 499
436 499
201...

output:

9
79 9 13 22 25 27 36 45 59 75 81 84 85 86 108 109 119 122 129 143 149 160 171 175 181 189 190 191 206 210 215 216 224 225 244 252 254 255 267 273 276 289 307 316 317 320 328 339 340 342 351 353 354 362 366 368 371 375 382 393 395 402 414 418 419 426 427 431 448 449 450 454 463 469 471 472 473 478 4...

result:

ok