QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#641878#3556. Making Friends on Joitter is FunElegia100 ✓861ms42200kbC++232.9kb2024-10-15 03:04:472024-10-15 03:04:54

Judging History

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

  • [2024-10-15 03:04:54]
  • 评测
  • 测评结果：100
  • 用时：861ms
  • 内存：42200kb
查看
  • [2024-10-15 03:04:47]
  • 提交

answer

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int N, M;
  cin >> N >> M;
  vector<int> f(N), sz(N, 1);
  iota(f.begin(), f.end(), 0);
  ll ans = 0;
  vector<set<int>> in(N);
  vector<vector<int>> vertices(N);
  for (int i = 0; i < N; ++i) vertices[i].push_back(i);
  function<int(int)> find = [&](int x) { return f[x] == x ? x : f[x] = find(f[x]); };
  set<pair<int, int>> ue;
  queue<pair<int, int>> q;
  auto check = [&](int x, int y) {
    ue.insert(make_pair(x, y));
    if (ue.count(make_pair(x, y)) && ue.count(make_pair(y, x)))
      q.emplace(x, y);
  };
  auto ade = [&](int u, int v) {
    v = find(v);
    if (find(u) == v) return;
    if (in[v].insert(u).second)
      ans += sz[v];
    check(find(u), v);
  };
  while (M--) {
    {
      int u, v;
      cin >> u >> v;
      ade(--u, --v);
    }
    while (!q.empty()) {
      int x, y;
      tie(x, y) = q.front(); q.pop();
      x = find(x); y = find(y);
      if (x == y) continue;
      if (sz[x] > sz[y]) swap(x, y);
      ans += sz[x] * (ll)sz[y] * 2;
      for (int v : vertices[x]) {
        if (in[y].erase(v))
          ans -= sz[y];
      }
      ans += in[y].size() * (ll)sz[x];
      for (int v : in[x]) {
        if (find(v) != y) {
          if (in[y].count(v))
            ans -= sz[x];
          else
            ade(v, y);
        } else
          ans -= sz[x];
      }
      in[x].clear();
      for (auto it = ue.lower_bound(make_pair(x, 0)); it != ue.end() && it->first == x; ue.erase(it++))
        if (find(it->second) != y && find(it->second) != x)
          check(y, it->second);
      vertices[y].insert(vertices[y].end(), vertices[x].begin(), vertices[x].end());
      vertices[x].clear();
      f[x] = y;
      sz[y] += sz[x];
    }
    cout << ans << '\n';
  }

#ifdef LBT
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}
源文件, 语言: C++23

详细

Subtask #1:

score: 1
Accepted

Test #1:

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

input:

5 20
4 2
1 5
2 3
2 5
3 2
3 1
4 5
1 2
5 2
1 4
4 1
3 4
5 1
2 4
2 1
4 3
1 3
5 4
3 5
5 3

output:

1
2
3
4
6
7
8
12
16
20
20
20
20
20
20
20
20
20
20
20

result:

ok 20 lines

Test #2:

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

input:

5 20
4 5
1 2
2 1
4 3
3 2
5 2
1 5
4 1
2 3
1 3
1 4
4 2
5 1
3 5
2 5
3 1
2 4
3 4
5 4
5 3

output:

1
2
3
4
6
8
13
13
16
16
20
20
20
20
20
20
20
20
20
20

result:

ok 20 lines

Test #3:

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

input:

5 20
3 1
5 1
3 4
5 2
1 2
5 4
3 5
2 4
1 3
2 5
4 5
4 3
4 2
2 3
3 2
5 3
2 1
1 5
4 1
1 4

output:

1
2
3
4
5
6
7
8
11
15
20
20
20
20
20
20
20
20
20
20

result:

ok 20 lines

Test #4:

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

input:

10 10
9 1
10 6
4 10
1 8
4 9
7 8
2 4
6 5
10 1
1 7

output:

1
2
3
4
5
6
7
8
9
10

result:

ok 10 lines

Test #5:

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

input:

10 90
10 6
7 8
8 4
9 3
2 8
9 2
1 10
1 8
8 9
5 6
2 10
4 3
7 2
10 2
10 5
3 7
1 9
8 7
1 2
9 1
7 6
9 7
10 3
8 3
6 3
7 5
8 2
6 1
4 9
7 1
4 2
6 8
7 3
9 8
5 1
10 4
6 4
1 4
6 7
3 1
9 10
3 2
1 7
2 5
10 1
2 7
2 1
5 8
7 9
2 4
6 9
3 8
10 7
8 5
5 4
8 6
5 10
3 5
5 7
8 1
4 7
4 1
10 8
9 5
4 8
6 10
1 6
2 9
1 5
6 5
3...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
17
18
19
20
52
52
59
60
60
60
60
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90

result:

ok 90 lines

Test #6:

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

input:

10 90
10 9
7 3
4 7
8 1
10 8
4 10
9 7
9 6
2 3
1 8
5 6
1 2
10 5
3 2
6 5
6 3
9 2
4 6
9 3
9 1
5 7
6 10
10 1
8 9
9 8
5 4
10 4
5 1
2 9
7 9
9 5
7 6
9 10
4 8
5 3
2 7
8 2
6 8
7 2
2 8
1 10
1 9
8 5
3 6
4 1
7 1
10 7
8 3
2 10
5 8
7 10
1 6
3 5
2 4
6 4
8 4
1 7
6 2
7 4
2 1
3 7
7 8
1 5
8 10
4 5
5 10
5 2
3 8
5 9
6 1
...

output:

1
2
3
4
5
6
7
8
9
11
12
13
14
17
20
22
24
26
26
28
29
35
35
49
49
55
55
55
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90

result:

ok 90 lines

Test #7:

score: 1
Accepted
time: 1ms
memory: 3540kb

input:

50 2450
21 49
31 13
28 21
35 9
40 19
8 18
8 41
13 46
5 2
46 9
30 46
37 36
4 19
23 33
28 39
2 23
38 28
13 26
46 44
29 27
35 15
10 23
49 33
2 6
16 22
2 10
29 15
18 5
15 40
46 29
18 47
31 5
9 45
18 29
15 27
40 27
12 43
14 22
8 31
50 29
16 4
35 43
36 40
16 34
28 14
30 13
9 40
44 47
33 36
10 29
26 33
8 1...

output:

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
99
100
101
102
103
106
109
110
113
114
115
116
117
118
119
120
121
12...

result:

ok 2450 lines

Test #8:

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

input:

50 2450
18 43
47 16
11 47
49 15
38 20
5 6
22 9
45 25
19 31
47 41
4 12
48 13
48 43
14 44
24 36
28 31
34 2
11 8
11 22
37 30
44 1
3 8
34 29
42 47
18 5
27 8
37 34
2 45
1 24
3 31
40 2
41 46
1 47
13 18
48 49
28 27
3 46
1 4
27 21
16 42
26 5
37 4
17 50
36 8
42 29
7 14
29 5
23 32
40 29
48 11
42 28
30 18
37 1...

output:

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
...

result:

ok 2450 lines

Test #9:

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

input:

50 2450
47 41
47 20
25 27
30 33
32 31
34 39
12 9
20 22
39 32
3 17
35 5
32 29
39 48
10 11
25 16
12 49
28 42
4 37
40 48
48 12
46 49
26 2
36 12
27 45
32 23
26 44
47 35
33 1
26 1
1 18
3 27
34 43
47 43
11 27
34 33
2 47
13 10
5 21
16 44
15 46
20 42
16 9
37 34
29 9
24 8
7 26
21 35
37 10
42 10
3 14
24 38
14...

output:

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
103
104
105
106...

result:

ok 2450 lines

Test #10:

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

input:

50 98
16 41
41 16
41 45
45 41
45 44
44 45
44 10
10 44
10 49
49 10
49 46
46 49
46 11
11 46
11 3
3 11
3 40
40 3
40 20
20 40
20 8
8 20
8 25
25 8
25 19
19 25
19 32
32 19
32 4
4 32
4 1
1 4
1 17
17 1
17 36
36 17
36 7
7 36
7 18
18 7
18 28
28 18
28 2
2 28
2 43
43 2
43 42
42 43
42 34
34 42
34 6
6 34
6 31
31 ...

output:

1
2
3
6
7
12
13
20
21
30
31
42
43
56
57
72
73
90
91
110
111
132
133
156
157
182
183
210
211
240
241
272
273
306
307
342
343
380
381
420
421
462
463
506
507
552
553
600
601
650
651
702
703
756
757
812
813
870
871
930
931
992
993
1056
1057
1122
1123
1190
1191
1260
1261
1332
1333
1406
1407
1482
1483
15...

result:

ok 98 lines

Test #11:

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

input:

50 98
33 15
44 28
46 16
25 8
43 44
36 10
22 24
20 29
23 31
13 42
1 45
15 33
10 36
7 46
50 37
44 43
1 28
32 26
11 3
17 14
38 18
25 49
30 5
14 17
37 35
22 3
46 7
36 20
3 22
34 32
15 40
4 33
28 1
30 19
2 49
11 26
45 1
4 12
27 7
5 8
26 11
19 30
16 46
24 14
14 24
6 38
40 15
47 48
5 30
35 37
47 43
23 21
2...

output:

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
30
31
32
34
36
37
38
39
43
44
46
47
49
50
54
56
60
61
65
66
69
71
73
74
86
87
89
90
91
92
95
97
101
107
108
110
111
114
126
136
137
138
141
144
147
151
163
165
166
172
190
225
236
237
244
247
282
290
338
466
530
558
566
574
6...

result:

ok 98 lines

Test #12:

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

input:

50 98
12 8
2 11
33 29
29 33
40 46
1 21
32 38
4 36
21 1
50 34
24 3
26 6
8 12
10 36
22 10
12 43
1 17
7 48
32 14
19 41
34 50
33 13
20 49
3 24
44 38
29 48
18 15
5 25
11 4
48 29
47 43
17 42
35 39
28 27
47 9
21 31
41 19
8 22
13 33
18 40
42 17
31 21
36 4
43 12
27 15
5 35
19 14
46 40
13 50
15 18
38 32
28 2
...

output:

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
34
35
36
37
38
39
40
41
42
48
49
51
54
57
62
63
64
65
67
69
71
73
74
77
78
81
82
86
93
94
95
98
100
101
104
105
113
114
115
117
122
124
126
128
130
150
162
171
173
174
177
183
191
212
238
288
316
332
356
361
511
559
564
58...

result:

ok 98 lines

Test #13:

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

input:

50 98
44 8
8 44
44 22
22 44
44 26
26 44
44 15
15 44
44 7
7 44
44 12
12 44
44 35
35 44
44 11
11 44
44 33
33 44
44 48
48 44
44 13
13 44
44 28
28 44
44 45
45 44
44 20
20 44
44 38
38 44
44 36
36 44
44 49
49 44
44 6
6 44
44 4
4 44
44 41
41 44
44 29
29 44
44 2
2 44
44 19
19 44
44 47
47 44
44 24
24 44
44 1...

output:

1
2
3
6
7
12
13
20
21
30
31
42
43
56
57
72
73
90
91
110
111
132
133
156
157
182
183
210
211
240
241
272
273
306
307
342
343
380
381
420
421
462
463
506
507
552
553
600
601
650
651
702
703
756
757
812
813
870
871
930
931
992
993
1056
1057
1122
1123
1190
1191
1260
1261
1332
1333
1406
1407
1482
1483
15...

result:

ok 98 lines

Test #14:

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

input:

50 98
2 30
2 9
2 4
2 31
2 33
2 18
30 2
2 22
2 27
2 35
27 2
2 43
2 45
2 21
10 2
2 44
2 38
20 2
44 2
2 42
2 41
2 23
9 2
16 2
2 7
15 2
2 46
2 19
2 26
39 2
2 47
2 1
2 32
2 48
38 2
24 2
45 2
2 36
2 49
2 16
2 17
50 2
2 24
37 2
2 8
2 14
2 37
40 2
2 15
2 3
12 2
4 2
19 2
22 2
48 2
46 2
3 2
2 13
29 2
2 40
2 5...

output:

1
2
3
4
5
6
7
8
9
10
13
14
15
16
19
20
21
24
31
32
33
34
43
48
49
54
55
56
57
62
63
64
65
66
80
86
103
104
105
117
118
126
139
148
149
150
164
174
189
190
201
228
257
288
321
356
393
394
411
434
435
476
519
564
611
633
683
684
736
766
821
822
879
938
999
1000
1063
1128
1195
1264
1335
1408
1443
1484
...

result:

ok 98 lines

Test #15:

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

input:

50 98
2 6
2 31
49 2
28 2
15 2
42 2
10 2
2 20
48 2
46 2
35 2
2 32
2 39
17 2
2 41
13 2
2 17
1 2
4 2
2 27
39 2
2 36
33 2
2 22
2 19
20 2
5 2
24 2
19 2
2 29
2 40
2 49
2 45
14 2
2 30
2 25
8 2
21 2
11 2
2 9
38 2
29 2
7 2
2 35
2 5
25 2
40 2
2 10
2 50
37 2
18 2
32 2
2 1
36 2
2 11
2 13
2 23
41 2
2 16
26 2
2 2...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
26
28
30
31
45
46
49
50
51
68
72
76
97
98
99
117
118
124
125
126
132
138
144
145
151
180
187
212
237
271
307
334
335
347
359
400
430
474
505
536
537
585
586
604
637
689
723
757
758
792
849
884
909
910
971
997
1035
1100
1139
1178
1217
1256
1288
1328
1401
1476
15...

result:

ok 98 lines

Test #16:

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

input:

50 98
41 13
13 41
41 35
35 41
13 26
26 13
26 25
25 26
41 27
27 41
27 14
14 27
41 5
5 41
13 40
40 13
5 21
21 5
26 12
12 26
27 22
22 27
5 9
9 5
22 29
29 22
14 20
20 14
21 11
11 21
14 32
32 14
21 23
23 21
13 50
50 13
23 48
48 23
26 36
36 26
13 10
10 13
48 46
46 48
32 28
28 32
32 31
31 32
22 6
6 22
40 1...

output:

1
2
3
6
7
12
13
20
21
30
31
42
43
56
57
72
73
90
91
110
111
132
133
156
157
182
183
210
211
240
241
272
273
306
307
342
343
380
381
420
421
462
463
506
507
552
553
600
601
650
651
702
703
756
757
812
813
870
871
930
931
992
993
1056
1057
1122
1123
1190
1191
1260
1261
1332
1333
1406
1407
1482
1483
15...

result:

ok 98 lines

Test #17:

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

input:

50 98
7 43
43 7
43 49
49 43
49 26
26 49
26 6
6 26
6 29
29 6
49 31
31 49
26 37
37 26
43 39
39 43
29 36
36 29
29 4
4 29
6 41
41 6
43 45
45 43
41 17
17 41
36 25
25 36
37 40
40 37
39 8
8 39
45 3
3 45
17 42
42 17
45 48
48 45
42 34
34 42
48 16
16 48
34 13
13 34
49 32
32 49
6 30
30 6
26 9
9 26
29 44
44 29
...

output:

1
2
3
6
7
12
13
20
21
30
31
42
43
56
57
72
73
90
91
110
111
132
133
156
157
182
183
210
211
240
241
272
273
306
307
342
343
380
381
420
421
462
463
506
507
552
553
600
601
650
651
702
703
756
757
812
813
870
871
930
931
992
993
1056
1057
1122
1123
1190
1191
1260
1261
1332
1333
1406
1407
1482
1483
15...

result:

ok 98 lines

Test #18:

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

input:

50 98
38 44
34 18
29 21
23 37
19 24
40 11
28 37
31 20
40 14
26 30
41 40
42 14
34 48
27 5
33 49
5 49
16 15
17 33
29 4
5 27
3 21
30 37
19 46
40 10
48 34
7 38
18 34
33 50
9 41
8 12
33 20
11 15
33 7
40 41
37 30
1 50
46 37
25 50
38 7
39 8
23 47
21 29
31 36
33 17
11 40
15 16
37 49
46 45
39 20
41 22
14 40
...

output:

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
29
30
31
32
33
34
35
37
41
42
44
45
47
48
49
51
52
53
57
59
60
61
62
63
72
79
84
88
89
95
99
121
129
130
160
161
164
165
166
176
186
193
204
228
229
230
256
257
259
270
281
292
352
361
373
413
557
581
620
625
666
692
720
743
810
15...

result:

ok 98 lines

Test #19:

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

input:

50 98
35 25
50 40
40 50
44 35
8 28
8 32
47 36
28 34
3 33
21 6
21 5
43 42
13 20
48 28
24 2
28 8
20 13
30 3
18 36
4 25
1 21
38 39
50 29
35 3
21 11
3 42
22 1
17 48
27 28
28 9
23 27
31 38
46 19
7 5
6 21
3 35
28 27
19 48
48 19
7 49
38 31
33 3
47 14
28 26
5 21
42 43
5 7
2 24
11 38
32 8
9 41
42 3
34 28
16 ...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
17
18
19
20
21
22
23
24
25
26
27
28
29
31
32
33
34
35
36
38
41
46
47
50
51
52
57
58
59
65
67
71
72
74
81
82
96
105
106
107
112
116
118
147
196
363
367
404
406
409
411
413
452
475
559
584
609
610
616
664
864
865
868
872
960
963
1146
1148
1149
1182
1215
1284
1290
12...

result:

ok 98 lines

Test #20:

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

input:

50 300
8 39
29 32
40 12
13 49
3 31
15 23
32 50
3 37
15 37
16 30
40 21
12 5
20 21
41 48
6 9
5 19
17 18
28 50
5 1
40 33
39 8
8 23
2 14
10 46
4 49
49 13
25 46
48 3
8 15
36 17
23 19
28 9
41 18
2 46
40 50
24 50
10 3
23 25
27 11
3 10
42 35
16 48
33 32
39 18
36 40
47 33
39 35
12 41
44 43
22 15
41 30
24 16
...

output:

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
42
43
44
45
46
47
48
49
50
51
52
53
54
55
57
59
60
62
63
64
66
67
68
69
70
72
74
75
76
77
78
79
80
81
82
83
84
87
88
89
90
92
93
94
95
96
97
98
99
101
102
103
104
105
106
107
108
109
110
111
1...

result:

ok 300 lines

Test #21:

score: 1
Accepted
time: 1ms
memory: 3624kb

input:

50 2450
25 12
17 19
11 5
9 31
32 10
41 35
36 6
34 36
32 22
30 16
24 32
33 10
38 19
14 12
44 15
24 45
4 27
7 8
22 49
44 20
24 33
36 40
37 22
22 17
2 49
33 42
40 45
3 30
23 27
28 38
33 7
40 16
44 27
13 11
27 22
48 42
30 39
11 31
38 21
38 45
47 9
6 17
7 25
38 46
22 35
16 40
18 33
30 5
20 7
8 31
3 26
10...

output:

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
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
100
101
102
103
104
105
...

result:

ok 2450 lines

Test #22:

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

input:

50 300
12 26
16 15
49 43
1 20
9 3
6 15
6 42
22 44
15 24
22 38
41 34
21 22
26 15
27 4
41 11
15 1
50 5
15 40
40 37
32 40
37 31
42 8
48 7
29 37
12 46
15 2
38 15
22 14
22 39
15 7
32 45
15 38
17 10
2 19
34 7
15 8
47 32
27 47
1 47
38 46
45 33
20 6
1 7
15 25
38 36
50 7
40 3
36 35
43 15
27 41
7 15
39 15
28 ...

output:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
54
55
81
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
106
240
275
276
277
278
279
280
281
282
283
283
314
328
329
397
497
498
565
565
566
566
567
592
592...

result:

ok 300 lines

Test #23:

score: 1
Accepted
time: 1ms
memory: 3620kb

input:

50 1080
35 30
2 47
28 30
41 32
26 24
36 17
47 12
9 35
9 18
34 35
23 46
28 10
29 46
47 9
7 13
44 17
43 14
5 40
27 34
49 25
20 19
24 16
5 44
35 22
44 25
6 1
36 49
47 39
5 25
7 8
13 30
13 40
15 3
19 8
1 45
30 24
48 50
11 48
33 3
38 19
32 40
13 45
5 50
30 46
25 20
1 28
29 26
28 36
45 47
31 33
49 41
10 1...

output:

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
...

result:

ok 1080 lines

Test #24:

score: 1
Accepted
time: 1ms
memory: 3548kb

input:

50 500
10 30
9 10
28 41
23 10
47 4
32 21
24 4
45 29
12 7
35 9
24 32
15 43
45 24
18 11
44 2
44 7
11 6
3 46
33 6
11 12
40 24
49 17
9 45
40 10
46 15
10 35
24 8
38 8
22 10
41 26
41 18
19 44
25 27
9 28
16 33
31 40
21 22
49 31
27 7
24 49
3 2
26 23
21 9
22 49
31 37
14 38
38 27
18 4
27 42
29 33
23 37
14 3
3...

output:

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
86
87
88
89
90
91
92
94
96
97
98
99
100
101
102
103
104
105
106
10...

result:

ok 500 lines

Test #25:

score: 1
Accepted
time: 1ms
memory: 3560kb

input:

50 2000
22 27
44 33
8 1
43 23
46 37
13 4
45 15
36 17
47 28
35 32
5 18
7 41
36 25
27 14
4 24
23 24
16 36
13 21
32 45
12 29
45 32
37 29
34 41
50 12
12 47
33 11
8 7
27 17
20 28
6 36
22 14
50 46
13 12
48 15
6 9
43 39
13 35
40 37
20 35
46 18
19 36
11 20
6 25
4 47
44 29
9 37
12 32
36 26
9 21
4 5
22 38
34 ...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
75
76
77
78
79
81
82
83
84
85
86
87
88
89
90
91
92
93
94
96
97
98
99
100
101
103
104
105
106
107
108
109
...

result:

ok 2000 lines

Test #26:

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

input:

50 98
49 13
13 48
48 49
48 24
24 13
24 15
15 13
48 45
45 13
13 27
27 49
27 16
16 24
45 22
22 16
22 28
28 24
45 8
8 28
13 25
25 8
24 41
41 13
16 6
6 25
15 47
47 24
8 36
36 6
36 5
5 22
5 34
34 27
22 38
38 45
15 33
33 5
22 44
44 49
8 18
18 41
36 21
21 24
34 1
1 8
34 30
30 27
5 39
39 41
1 37
37 33
15 2
...

output:

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
2450

result:

ok 98 lines

Test #27:

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

input:

50 98
43 10
10 37
37 43
43 14
14 10
43 23
23 14
37 30
30 23
37 44
44 10
10 16
16 43
16 20
20 10
14 15
15 43
44 32
32 14
44 34
34 10
30 35
35 44
14 9
9 15
14 25
25 34
43 11
11 25
44 8
8 35
16 13
13 9
20 18
18 25
23 41
41 44
9 29
29 25
20 6
6 25
16 39
39 6
10 46
46 41
18 31
31 15
32 36
36 44
6 7
7 36
...

output:

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
2450

result:

ok 98 lines

Test #28:

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

input:

50 98
31 8
8 6
6 31
31 14
14 6
14 17
17 6
8 41
41 17
41 18
18 8
14 12
12 18
41 16
16 12
16 3
3 6
3 33
33 6
17 11
11 33
11 30
30 31
18 9
9 30
14 32
32 9
31 7
7 32
16 24
24 7
14 13
13 24
13 49
49 33
49 23
23 24
23 2
2 13
18 25
25 2
25 15
15 23
15 34
34 13
3 48
48 34
48 40
40 12
24 29
29 40
29 46
46 18...

output:

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
2450

result:

ok 98 lines

Test #29:

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

input:

50 98
20 19
19 12
12 20
19 6
6 12
6 46
46 19
6 42
42 46
19 14
14 42
46 37
37 14
37 48
48 20
46 16
16 48
16 25
25 48
42 26
26 25
26 30
30 37
16 22
22 30
26 9
9 22
9 11
11 19
20 10
10 11
9 2
2 10
2 28
28 9
28 32
32 48
32 17
17 37
17 4
4 32
28 31
31 4
16 36
36 31
19 40
40 36
40 1
1 30
1 13
13 11
11 44
...

output:

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
2450

result:

ok 98 lines

Test #30:

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

input:

50 110
50 21
21 50
38 4
4 38
7 45
45 7
9 12
12 9
42 14
14 42
27 13
13 27
47 34
34 47
17 30
30 17
10 18
18 10
35 5
5 35
11 28
28 11
15 2
2 15
49 29
29 49
44 1
1 44
33 23
23 33
26 6
6 26
40 36
36 40
25 22
22 25
46 24
24 46
20 48
48 20
3 31
31 3
41 8
8 41
39 43
43 39
19 32
32 19
37 16
16 37
50 38
38 50...

output:

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
52
58
60
66
68
74
76
82
84
90
92
98
100
106
108
114
116
122
124
130
132
138
140
146
150
178
182
210
214
242
246
274
278
306
310
338
346
466
474
594
602
722
738...

result:

ok 110 lines

Test #31:

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

input:

50 2000
40 13
13 40
45 14
14 45
33 46
46 33
17 37
37 17
12 43
43 12
39 47
47 39
34 3
3 34
49 4
4 49
20 6
6 20
18 1
1 18
24 48
48 24
2 25
25 2
21 7
7 21
26 38
38 26
9 35
35 9
41 5
5 41
28 29
29 28
30 44
44 30
19 11
11 19
15 8
8 15
27 16
16 27
36 10
10 36
42 22
22 42
23 50
50 23
32 31
31 32
40 45
45 4...

output:

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
52
58
60
66
68
74
76
82
84
90
92
98
100
106
108
114
116
122
124
130
132
138
140
146
150
178
182
210
214
242
246
274
278
306
310
338
346
466
474
594
602
722
738...

result:

ok 2000 lines

Test #32:

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

input:

50 110
5 24
47 27
15 16
25 46
9 37
29 36
38 34
18 11
40 27
34 5
6 2
5 43
36 33
14 23
23 24
46 19
46 33
2 6
5 3
27 47
24 16
11 2
20 5
11 31
10 27
16 36
48 42
27 40
49 44
44 40
40 21
24 23
46 3
16 15
30 3
27 26
5 34
26 12
43 5
32 30
36 16
24 5
19 41
25 8
44 37
8 25
4 43
38 27
11 24
4 1
40 44
37 44
18 ...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
21
22
24
25
26
28
29
30
33
34
37
38
41
42
44
45
46
49
50
55
56
62
79
80
81
82
83
88
91
96
97
105
119
120
167
171
184
186
188
192
193
255
256
273
274
275
280
285
297
315
317
335
336
337
338
356
370
371
374
374
384
385
418
453
454
471
490
491
492
500
506...

result:

ok 110 lines

Test #33:

score: 1
Accepted
time: 1ms
memory: 3780kb

input:

50 2000
5 40
43 27
15 17
30 42
45 7
3 42
30 24
5 18
18 27
6 19
20 44
30 23
29 12
13 39
25 40
33 46
14 19
40 35
21 18
20 40
19 15
3 32
49 43
44 27
9 31
43 50
4 42
34 8
3 38
50 45
13 47
47 50
47 37
28 10
23 39
36 7
44 48
47 44
28 44
28 42
29 27
19 43
35 48
44 22
23 50
13 30
48 49
16 42
33 45
50 42
49 ...

output:

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
85
86
87
88
89
90
91
92
93
95
96
98
99
100
101
102
103
104
1...

result:

ok 2000 lines

Subtask #2:

score: 16
Accepted

Dependency #1:

100%
Accepted

Test #34:

score: 16
Accepted
time: 2ms
memory: 3592kb

input:

100 9900
100 84
62 32
63 36
5 17
19 87
49 31
50 42
31 74
66 10
36 17
41 67
20 30
72 100
92 56
18 76
87 72
56 52
1 54
27 17
86 32
17 54
50 43
54 28
98 66
36 14
59 17
97 92
24 39
94 88
12 55
66 62
49 17
64 58
13 40
69 68
51 23
3 51
59 46
19 81
46 48
59 52
59 7
51 88
24 5
14 60
8 15
26 6
42 68
35 8
27 ...

output:

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
...

result:

ok 9900 lines

Test #35:

score: 16
Accepted
time: 46ms
memory: 4628kb

input:

1000 300000
453 351
53 528
84 713
510 908
622 719
273 26
3 502
14 269
161 385
972 491
197 403
274 700
826 753
99 83
292 471
702 814
729 878
679 892
57 562
858 935
272 86
191 782
608 235
379 435
259 817
244 426
774 297
127 306
594 381
546 903
46 355
275 204
972 385
680 521
610 353
46 846
544 154
68 7...

output:

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
...

result:

ok 300000 lines

Test #36:

score: 16
Accepted
time: 64ms
memory: 6168kb

input:

2000 300000
1499 798
1978 265
1304 1446
1798 1806
927 1981
1844 967
1323 610
993 68
1109 931
1933 319
228 704
1313 300
1548 1411
451 1790
787 914
580 1739
1516 219
918 362
140 885
486 1700
1235 1271
287 707
1032 515
933 844
1036 1912
564 913
1134 1426
1160 1844
547 1846
823 1391
664 272
866 64
794 8...

output:

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
...

result:

ok 300000 lines

Test #37:

score: 16
Accepted
time: 70ms
memory: 6224kb

input:

2000 300000
1384 813
1538 1621
1523 427
842 1051
1995 1280
928 1312
525 132
1271 1984
1557 1974
1805 1170
835 684
50 1896
1463 1726
1404 458
1819 1387
36 1266
513 706
413 517
1405 468
250 15
936 1241
531 1119
937 1731
754 252
680 1333
414 1119
1536 746
1134 1112
466 1191
1334 1056
760 341
76 1851
63...

output:

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
...

result:

ok 300000 lines

Test #38:

score: 16
Accepted
time: 65ms
memory: 5964kb

input:

2000 300000
42 1133
1954 122
1120 709
273 690
1051 1909
1248 1608
1256 724
1376 989
587 630
1319 1882
139 1483
1071 1717
1346 687
799 389
1038 177
1734 739
1482 1343
1101 1576
1076 1876
683 1123
112 323
968 1071
1175 297
77 1301
1213 1582
1468 1802
7 1941
1630 819
668 474
721 1334
1093 871
1697 1931...

output:

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
...

result:

ok 300000 lines

Test #39:

score: 16
Accepted
time: 2ms
memory: 3936kb

input:

2000 3998
854 1714
1714 854
1714 56
56 1714
56 649
649 56
649 1676
1676 649
1676 1631
1631 1676
1631 1039
1039 1631
1039 1980
1980 1039
1980 1566
1566 1980
1566 1642
1642 1566
1642 1945
1945 1642
1945 454
454 1945
454 277
277 454
277 351
351 277
351 1957
1957 351
1957 998
998 1957
998 704
704 998
70...

output:

1
2
3
6
7
12
13
20
21
30
31
42
43
56
57
72
73
90
91
110
111
132
133
156
157
182
183
210
211
240
241
272
273
306
307
342
343
380
381
420
421
462
463
506
507
552
553
600
601
650
651
702
703
756
757
812
813
870
871
930
931
992
993
1056
1057
1122
1123
1190
1191
1260
1261
1332
1333
1406
1407
1482
1483
15...

result:

ok 3998 lines

Test #40:

score: 16
Accepted
time: 4ms
memory: 3940kb

input:

2000 3998
570 1493
1251 1275
1026 12
260 787
1813 1548
427 14
1133 762
1941 854
1750 1342
368 1974
1294 1741
1087 1292
1934 144
1853 182
1154 274
1522 975
104 57
24 1958
1564 1130
557 187
1262 1686
398 318
66 1915
740 384
1574 1999
1926 614
1817 571
179 108
346 536
914 273
1769 1587
1588 1727
1715 1...

output:

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
...

result:

ok 3998 lines

Test #41:

score: 16
Accepted
time: 2ms
memory: 3960kb

input:

2000 3998
1672 1764
1610 966
970 1820
1623 699
1611 1483
1595 1250
1091 172
1708 898
1927 1208
436 1738
961 801
623 1247
1732 1089
1265 639
848 299
124 301
974 923
23 916
772 192
1483 1874
853 386
1318 18
216 1799
1840 1574
387 1182
1721 1616
858 357
364 154
486 942
1736 994
1682 1831
1022 1023
859 ...

output:

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
...

result:

ok 3998 lines

Test #42:

score: 16
Accepted
time: 2ms
memory: 4080kb

input:

2000 3998
947 954
954 947
947 1620
1620 947
947 960
960 947
947 149
149 947
947 1406
1406 947
947 80
80 947
947 1906
1906 947
947 808
808 947
947 1948
1948 947
947 1257
1257 947
947 1012
1012 947
947 811
811 947
947 1361
1361 947
947 753
753 947
947 1962
1962 947
947 884
884 947
947 927
927 947
947 ...

output:

1
2
3
6
7
12
13
20
21
30
31
42
43
56
57
72
73
90
91
110
111
132
133
156
157
182
183
210
211
240
241
272
273
306
307
342
343
380
381
420
421
462
463
506
507
552
553
600
601
650
651
702
703
756
757
812
813
870
871
930
931
992
993
1056
1057
1122
1123
1190
1191
1260
1261
1332
1333
1406
1407
1482
1483
15...

result:

ok 3998 lines

Test #43:

score: 16
Accepted
time: 3ms
memory: 3900kb

input:

2000 3998
1388 1305
865 1388
1388 1139
1388 1599
1388 1162
46 1388
1395 1388
1087 1388
1388 350
1459 1388
1388 1924
1388 1283
1335 1388
872 1388
1388 1069
776 1388
1892 1388
1216 1388
1388 985
1388 872
140 1388
1388 1526
1388 399
1388 1792
1388 793
1388 952
50 1388
1388 494
1354 1388
1388 1715
1388 ...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
29
31
32
33
34
35
36
38
39
41
42
43
44
46
47
48
49
51
52
53
55
57
58
59
60
61
62
64
65
67
69
71
73
74
75
77
78
80
82
84
86
88
90
92
93
94
95
97
99
100
102
103
104
106
107
108
142
143
146
149
152
153
154
157
195
196
197
198
199
200
201
202
206
210
211
2...

result:

ok 3998 lines

Test #44:

score: 16
Accepted
time: 0ms
memory: 4152kb

input:

2000 3998
542 381
542 95
667 542
596 542
542 1061
542 1588
542 1812
168 542
660 542
542 1591
542 34
1408 542
1022 542
542 132
225 542
1076 542
332 542
542 1
542 537
542 312
542 1823
542 428
542 1423
542 604
1068 542
542 1113
542 1683
376 542
1364 542
542 1848
542 696
1708 542
1439 542
542 1872
542 2...

output:

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
...

result:

ok 3998 lines

Test #45:

score: 16
Accepted
time: 2ms
memory: 4160kb

input:

2000 3998
1446 1586
1586 1446
1446 1428
1428 1446
1446 118
118 1446
1586 1033
1033 1586
1446 300
300 1446
1446 1631
1631 1446
300 914
914 300
118 1554
1554 118
914 28
28 914
914 1793
1793 914
300 1394
1394 300
1446 845
845 1446
1446 1774
1774 1446
1428 1995
1995 1428
118 822
822 118
1446 1261
1261 1...

output:

1
2
3
6
7
12
13
20
21
30
31
42
43
56
57
72
73
90
91
110
111
132
133
156
157
182
183
210
211
240
241
272
273
306
307
342
343
380
381
420
421
462
463
506
507
552
553
600
601
650
651
702
703
756
757
812
813
870
871
930
931
992
993
1056
1057
1122
1123
1190
1191
1260
1261
1332
1333
1406
1407
1482
1483
15...

result:

ok 3998 lines

Test #46:

score: 16
Accepted
time: 2ms
memory: 3924kb

input:

2000 3998
486 1522
1522 486
1522 37
37 1522
1522 1810
1810 1522
37 1634
1634 37
1810 1260
1260 1810
37 1480
1480 37
1480 121
121 1480
1810 662
662 1810
37 933
933 37
933 274
274 933
1480 167
167 1480
167 515
515 167
1480 972
972 1480
1634 1993
1993 1634
1810 746
746 1810
1480 1359
1359 1480
1993 166...

output:

1
2
3
6
7
12
13
20
21
30
31
42
43
56
57
72
73
90
91
110
111
132
133
156
157
182
183
210
211
240
241
272
273
306
307
342
343
380
381
420
421
462
463
506
507
552
553
600
601
650
651
702
703
756
757
812
813
870
871
930
931
992
993
1056
1057
1122
1123
1190
1191
1260
1261
1332
1333
1406
1407
1482
1483
15...

result:

ok 3998 lines

Test #47:

score: 16
Accepted
time: 2ms
memory: 4148kb

input:

2000 3998
1718 855
753 650
630 395
1532 1576
495 1460
709 1378
729 1678
1388 585
987 1711
1806 1053
1761 1369
1591 173
340 843
624 87
812 230
1043 405
1186 1980
1037 1121
926 1625
441 448
1163 808
1499 1194
1993 1482
1666 562
1856 77
775 1986
25 1248
1918 1917
407 200
14 917
1343 388
1244 1299
916 1...

output:

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
...

result:

ok 3998 lines

Test #48:

score: 16
Accepted
time: 4ms
memory: 4212kb

input:

2000 3998
911 607
187 798
1347 1962
287 1135
751 706
698 981
1273 1770
1346 807
1713 1847
114 1069
224 878
206 156
614 822
476 1929
1750 159
1422 1268
1198 500
1895 636
1338 592
962 1046
1426 1496
1108 597
912 1414
1540 52
1072 222
569 1252
287 1903
155 1102
1736 309
1263 1561
1602 339
653 544
109 2...

output:

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
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...

result:

ok 3998 lines

Test #49:

score: 16
Accepted
time: 6ms
memory: 4452kb

input:

2000 10000
1475 522
1380 1975
553 474
1359 1744
1531 383
1595 765
1804 1881
1822 82
389 807
213 1178
1749 143
1903 244
718 1546
429 125
1791 1249
587 1276
1124 242
1067 1048
537 534
1575 548
1281 431
1763 767
178 195
38 593
1171 629
1751 1777
941 1658
1223 627
1412 1338
83 469
1105 328
1370 1739
140...

output:

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
...

result:

ok 10000 lines

Test #50:

score: 16
Accepted
time: 66ms
memory: 6160kb

input:

2000 300000
1782 1085
628 315
1513 1984
519 1921
1817 2000
1545 1071
1318 1523
1329 1521
226 1374
315 614
1872 2000
1286 594
57 1170
825 844
784 230
890 1396
371 735
462 201
815 1527
1783 1001
1911 1694
68 1460
2000 382
755 423
1270 1229
1676 1677
1918 681
911 1075
1120 1458
1875 227
826 1874
1414 1...

output:

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
...

result:

ok 300000 lines

Test #51:

score: 16
Accepted
time: 6ms
memory: 4272kb

input:

2000 10000
374 1452
455 203
455 164
446 386
1648 455
1953 537
397 193
1619 640
356 455
1911 455
1570 600
455 312
274 659
1363 1750
111 1172
455 1763
1575 842
632 1041
1266 209
455 118
726 559
744 775
455 26
1617 349
1188 651
455 1073
262 730
280 455
1212 789
1795 455
1290 455
444 1812
455 1026
962 1...

output:

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
121
...

result:

ok 10000 lines

Test #52:

score: 16
Accepted
time: 57ms
memory: 5068kb

input:

2000 300000
939 563
1555 83
160 1679
407 1293
1478 1977
1216 1350
189 767
455 933
1972 1012
1091 503
895 1360
205 1352
1057 396
1820 73
1137 1616
562 1346
123 1134
546 1276
472 297
1038 187
1310 174
578 1071
1227 1747
314 1812
728 1772
809 955
925 1251
1151 1307
233 1176
1607 305
1404 1310
1340 693
...

output:

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
...

result:

ok 300000 lines

Test #53:

score: 16
Accepted
time: 9ms
memory: 4308kb

input:

2000 10000
1220 762
871 862
408 483
195 1270
170 1972
1237 392
514 745
224 1747
1395 1260
51 1069
96 1949
615 259
455 998
537 73
1883 1626
808 1539
1450 1583
472 1543
1567 843
1306 741
40 405
1017 1129
1696 826
361 1875
621 1257
1752 454
1689 1059
1197 513
1518 1063
461 1763
1841 931
797 1581
73 537...

output:

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
...

result:

ok 10000 lines

Test #54:

score: 16
Accepted
time: 61ms
memory: 5612kb

input:

2000 300000
1713 1793
1450 1268
966 1169
1309 917
436 249
1036 905
381 1152
368 859
566 486
1953 109
682 1619
32 953
1043 612
837 1270
1545 742
1389 753
260 916
1023 181
212 1718
1555 1959
363 1009
548 1640
658 1895
1158 483
910 1399
1153 1430
114 1577
815 9
1621 811
1330 1132
1276 1691
29 1422
1803...

output:

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
...

result:

ok 300000 lines

Test #55:

score: 16
Accepted
time: 5ms
memory: 4140kb

input:

2000 3998
750 1861
750 1415
1415 1861
1861 102
102 750
1861 962
962 1415
962 713
713 1861
750 480
480 713
750 943
943 1861
962 1086
1086 1415
750 782
782 102
1086 379
379 782
102 701
701 1861
102 370
370 750
782 173
173 1086
750 862
862 962
862 784
784 701
784 965
965 102
782 116
116 965
750 225
225...

output:

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
...

result:

ok 3998 lines

Test #56:

score: 16
Accepted
time: 5ms
memory: 4208kb

input:

2000 3998
1433 1987
1433 1582
1582 1987
1582 76
76 1433
1582 896
896 76
896 1870
1870 1433
76 1040
1040 1987
1040 276
276 1582
1582 1837
1837 896
1870 875
875 1987
1582 1835
1835 76
276 795
795 1837
795 1167
1167 76
1433 871
871 1835
1167 1508
1508 76
795 1346
1346 76
896 1983
1983 1837
276 261
261 ...

output:

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
...

result:

ok 3998 lines

Test #57:

score: 16
Accepted
time: 5ms
memory: 4400kb

input:

2000 3998
920 764
920 123
123 764
920 1739
1739 123
920 554
554 1739
554 1149
1149 123
123 331
331 1149
764 1529
1529 331
1529 268
268 123
268 1711
1711 764
764 673
673 1711
764 1040
1040 673
1040 1933
1933 1711
331 541
541 1933
541 1542
1542 1149
1542 1129
1129 673
1129 315
315 673
1542 344
344 315...

output:

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
...

result:

ok 3998 lines

Test #58:

score: 16
Accepted
time: 5ms
memory: 4368kb

input:

2000 3998
131 447
131 1182
1182 447
447 1481
1481 1182
1481 1046
1046 131
1046 783
783 131
783 1811
1811 1481
1811 1471
1471 1046
1471 508
508 1811
508 1266
1266 783
1266 1023
1023 1046
1471 1550
1550 1023
1811 1743
1743 1550
1743 488
488 1046
488 1053
1053 1481
1053 55
55 508
55 250
250 1471
1471 1...

output:

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
...

result:

ok 3998 lines

Test #59:

score: 16
Accepted
time: 3ms
memory: 3872kb

input:

2000 4500
647 1683
1683 647
1836 1497
1497 1836
1249 1663
1663 1249
1198 1054
1054 1198
198 1689
1689 198
1184 978
978 1184
245 1893
1893 245
1171 1609
1609 1171
1104 80
80 1104
993 1336
1336 993
1192 738
738 1192
1604 460
460 1604
782 1278
1278 782
1086 1231
1231 1086
981 191
191 981
1672 1687
1687...

output:

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
...

result:

ok 4500 lines

Test #60:

score: 16
Accepted
time: 40ms
memory: 3928kb

input:

2000 300000
1204 884
884 1204
634 923
923 634
497 421
421 497
355 1556
1556 355
1627 982
982 1627
761 1068
1068 761
1005 76
76 1005
806 1866
1866 806
1850 1362
1362 1850
1855 1903
1903 1855
709 1142
1142 709
1514 1667
1667 1514
1340 1030
1030 1340
799 1696
1696 799
726 738
738 726
711 1129
1129 711
...

output:

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
...

result:

ok 300000 lines

Test #61:

score: 16
Accepted
time: 2ms
memory: 4024kb

input:

2000 4500
1939 906
206 940
1581 74
277 1602
1904 942
1261 175
632 708
997 336
1917 1214
475 976
187 1102
1236 438
578 1996
1620 1777
916 1329
1524 1932
212 1619
1829 905
613 309
1376 62
467 676
1291 189
1760 1522
1740 1079
796 1802
1288 1599
1868 24
756 1105
435 19
1452 1678
1498 1079
1630 998
1068 ...

output:

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
...

result:

ok 4500 lines

Test #62:

score: 16
Accepted
time: 60ms
memory: 5772kb

input:

2000 300000
1044 968
299 1424
271 346
106 228
1135 693
1958 342
134 1600
1343 1018
1334 189
724 232
560 491
1770 1545
250 640
240 760
353 826
1139 1483
396 81
320 1563
421 987
1614 1506
108 1615
1126 1370
1904 779
756 911
1829 218
1876 857
494 1599
1590 1842
179 417
1330 1255
507 1922
1729 481
576 2...

output:

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
...

result:

ok 300000 lines

Subtask #3:

score: 83
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #63:

score: 83
Accepted
time: 342ms
memory: 42092kb

input:

100000 300000
31635 79749
51055 63168
40834 34514
63501 80992
38971 50404
761 92653
55492 28017
81252 20910
8603 79430
51705 36089
85269 45799
68856 82580
46272 25786
30700 24046
99751 43497
88907 57433
81510 24845
61303 60574
17929 65794
60466 46363
30125 80303
26445 93529
25503 35541
61168 49245
5...

output:

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
...

result:

ok 300000 lines

Test #64:

score: 83
Accepted
time: 372ms
memory: 42112kb

input:

100000 300000
50469 22921
30052 43429
59634 52087
60632 71682
89414 43314
82674 64122
45534 66553
89973 85874
51060 70828
34715 61023
9679 19078
37079 69053
17023 52713
79859 71829
91597 86420
44 51670
76018 68
92654 31815
87222 15811
92117 97924
89730 89618
33265 58426
68361 83468
12675 37027
5669 ...

output:

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
...

result:

ok 300000 lines

Test #65:

score: 83
Accepted
time: 347ms
memory: 42200kb

input:

100000 300000
12544 51007
35587 68143
69021 29672
75249 89162
17406 55174
67218 79046
28419 73912
32206 86079
74046 66080
53128 96098
40952 71544
73680 38388
86606 83488
8642 92369
79128 81119
26266 70893
96280 92873
28323 919
39298 42197
33679 33539
21652 1510
52534 77617
59084 54099
79521 34131
30...

output:

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
...

result:

ok 300000 lines

Test #66:

score: 83
Accepted
time: 102ms
memory: 19140kb

input:

100000 199998
41096 66490
66490 41096
66490 38978
38978 66490
38978 97869
97869 38978
97869 94422
94422 97869
94422 55704
55704 94422
55704 32765
32765 55704
32765 62737
62737 32765
62737 78650
78650 62737
78650 25190
25190 78650
25190 39753
39753 25190
39753 43256
43256 39753
43256 24561
24561 4325...

output:

1
2
3
6
7
12
13
20
21
30
31
42
43
56
57
72
73
90
91
110
111
132
133
156
157
182
183
210
211
240
241
272
273
306
307
342
343
380
381
420
421
462
463
506
507
552
553
600
601
650
651
702
703
756
757
812
813
870
871
930
931
992
993
1056
1057
1122
1123
1190
1191
1260
1261
1332
1333
1406
1407
1482
1483
15...

result:

ok 199998 lines

Test #67:

score: 83
Accepted
time: 296ms
memory: 23352kb

input:

100000 199998
61928 41730
14355 646
18505 27710
78626 24163
35266 76094
57511 55766
10828 37799
526 49093
95779 76454
49599 66638
96468 83745
10506 35829
59699 4242
95317 70465
40789 20029
75659 36383
45744 72064
91656 63484
65526 40515
57393 17885
2568 71086
84098 69969
326 23676
59775 72772
93436 ...

output:

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
...

result:

ok 199998 lines

Test #68:

score: 83
Accepted
time: 108ms
memory: 19096kb

input:

100000 199998
56438 61876
61876 56438
56438 27418
27418 56438
56438 10437
10437 56438
56438 81563
81563 56438
56438 62932
62932 56438
56438 42082
42082 56438
56438 46706
46706 56438
56438 95089
95089 56438
56438 76399
76399 56438
56438 756
756 56438
56438 63269
63269 56438
56438 78553
78553 56438
56...

output:

1
2
3
6
7
12
13
20
21
30
31
42
43
56
57
72
73
90
91
110
111
132
133
156
157
182
183
210
211
240
241
272
273
306
307
342
343
380
381
420
421
462
463
506
507
552
553
600
601
650
651
702
703
756
757
812
813
870
871
930
931
992
993
1056
1057
1122
1123
1190
1191
1260
1261
1332
1333
1406
1407
1482
1483
15...

result:

ok 199998 lines

Test #69:

score: 83
Accepted
time: 221ms
memory: 20804kb

input:

100000 199998
60042 84312
85181 60042
31370 60042
62998 60042
91364 60042
11886 60042
74514 60042
60042 9161
98661 60042
63860 60042
85021 60042
60042 68070
43223 60042
60042 64811
60042 66603
60042 78491
60042 83665
15250 60042
63396 60042
60042 78622
60042 47774
60042 71610
43717 60042
60042 2984
...

output:

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
...

result:

ok 199998 lines

Test #70:

score: 83
Accepted
time: 105ms
memory: 19156kb

input:

100000 199998
97123 18009
18009 97123
18009 35088
35088 18009
35088 40153
40153 35088
18009 69297
69297 18009
18009 39846
39846 18009
40153 75327
75327 40153
75327 86146
86146 75327
40153 38485
38485 40153
86146 83222
83222 86146
39846 53208
53208 39846
38485 32917
32917 38485
18009 94589
94589 1800...

output:

1
2
3
6
7
12
13
20
21
30
31
42
43
56
57
72
73
90
91
110
111
132
133
156
157
182
183
210
211
240
241
272
273
306
307
342
343
380
381
420
421
462
463
506
507
552
553
600
601
650
651
702
703
756
757
812
813
870
871
930
931
992
993
1056
1057
1122
1123
1190
1191
1260
1261
1332
1333
1406
1407
1482
1483
15...

result:

ok 199998 lines

Test #71:

score: 83
Accepted
time: 115ms
memory: 19336kb

input:

100000 199998
22622 32537
32537 22622
22622 1119
1119 22622
22622 79248
79248 22622
22622 54377
54377 22622
54377 29049
29049 54377
79248 45634
45634 79248
29049 3245
3245 29049
1119 94935
94935 1119
45634 67977
67977 45634
45634 38409
38409 45634
94935 2866
2866 94935
2866 21774
21774 2866
94935 41...

output:

1
2
3
6
7
12
13
20
21
30
31
42
43
56
57
72
73
90
91
110
111
132
133
156
157
182
183
210
211
240
241
272
273
306
307
342
343
380
381
420
421
462
463
506
507
552
553
600
601
650
651
702
703
756
757
812
813
870
871
930
931
992
993
1056
1057
1122
1123
1190
1191
1260
1261
1332
1333
1406
1407
1482
1483
15...

result:

ok 199998 lines

Test #72:

score: 83
Accepted
time: 305ms
memory: 21844kb

input:

100000 199998
5490 33039
31045 47462
17877 73396
45324 4043
52370 76069
49361 29513
63758 99630
78634 76141
59073 13070
97416 32446
73795 10988
47863 79936
74287 2158
89362 61615
53370 53136
62602 65811
95151 84751
13797 26143
51878 35562
14285 27299
31418 41100
8911 84681
31569 43520
75731 26930
79...

output:

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
...

result:

ok 199998 lines

Test #73:

score: 83
Accepted
time: 306ms
memory: 22084kb

input:

100000 199998
90908 68691
24424 32125
89565 95394
57462 81738
30501 22771
27628 57660
36188 8027
12724 55073
36194 35459
8951 42783
46276 5847
78701 80044
19048 68604
83694 61550
97237 6564
67164 41667
56580 28332
40892 98935
54391 72000
75944 59577
36303 39721
51903 27568
73903 91335
15176 17145
21...

output:

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
...

result:

ok 199998 lines

Test #74:

score: 83
Accepted
time: 861ms
memory: 32924kb

input:

100000 300000
39972 5059
67300 65997
51836 35059
29634 59727
13262 26136
13859 76806
49862 85575
76297 60405
57237 49470
18775 52698
76091 51274
41093 2508
83485 75188
25969 70553
81325 28850
60860 11058
43021 86959
4141 89225
31425 31686
90495 34550
87092 46620
17133 72985
42374 98793
92525 85644
7...

output:

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
...

result:

ok 300000 lines

Test #75:

score: 83
Accepted
time: 327ms
memory: 23324kb

input:

100000 300000
86666 11553
11553 48360
73235 86659
11553 51034
11553 45896
46928 41843
70777 11553
90441 55288
11553 65174
11553 46816
11553 50968
86082 69977
11553 13024
4408 11553
29545 11553
56140 30720
5804 11553
11553 12473
11553 62545
7428 11553
15557 11553
11553 30987
95390 11553
3572 84640
60...

output:

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
...

result:

ok 300000 lines

Test #76:

score: 83
Accepted
time: 519ms
memory: 29152kb

input:

100000 300000
70877 68505
76173 13112
53164 30538
36530 41329
22340 38602
31144 56049
89364 24146
88960 13760
32223 79604
10767 95723
19871 57806
80365 17868
26543 56711
83641 25286
76674 11621
67889 52199
95838 88289
68962 75896
30950 13707
28089 16139
85205 84072
94680 23390
72808 2232
98397 37119...

output:

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
...

result:

ok 300000 lines

Test #77:

score: 83
Accepted
time: 541ms
memory: 29672kb

input:

100000 300000
15345 98204
88357 63730
96131 48589
40046 59134
40315 2450
97762 83199
95113 84751
50151 17436
3568 67552
6512 92733
35775 48154
77455 2630
64836 83355
72845 26277
12364 87276
55516 8321
91718 68236
19621 73829
99563 43250
88441 41175
47005 645
12651 5519
76050 20047
31863 95748
66166 ...

output:

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
...

result:

ok 300000 lines

Test #78:

score: 83
Accepted
time: 124ms
memory: 21520kb

input:

100000 155000
94690 88639
94690 723
94690 60487
94690 7630
94690 87422
94690 53359
94690 606
94690 1509
94690 267
94690 91891
94690 36126
94690 3071
94690 20264
94690 94996
94690 896
94690 60192
94690 12723
94690 9137
94690 64671
94690 49836
94690 8498
94690 38146
94690 62845
94690 95809
94690 30144...

output:

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
...

result:

ok 155000 lines

Test #79:

score: 83
Accepted
time: 214ms
memory: 22164kb

input:

100000 300000
41700 43971
41700 11523
41700 49359
41700 63797
41700 7016
41700 42143
41700 68658
41700 28753
41700 63529
41700 83680
41700 29148
41700 47066
41700 2117
41700 67411
41700 29683
41700 53351
41700 55292
41700 27522
41700 14943
41700 79077
41700 12852
41700 28294
41700 38101
41700 54370
...

output:

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
...

result:

ok 300000 lines

Test #80:

score: 83
Accepted
time: 179ms
memory: 23852kb

input:

100000 155000
49258 51968
53086 51968
99795 51968
89041 51968
71123 51968
454 51968
89711 51968
21870 51968
6794 51968
51369 51968
60202 51968
42466 51968
6321 51968
44032 51968
64904 51968
43125 51968
30811 51968
31255 51968
71260 51968
80058 51968
85660 51968
32434 51968
8642 51968
3114 51968
4468...

output:

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
...

result:

ok 155000 lines

Test #81:

score: 83
Accepted
time: 312ms
memory: 24100kb

input:

100000 300000
96369 92965
73666 92965
35913 92965
52236 92965
3122 92965
48222 92965
3885 92965
96441 92965
10940 92965
38843 92965
53520 92965
70539 92965
71697 92965
58856 92965
86598 92965
3378 92965
59072 92965
27416 92965
26501 92965
53709 92965
49083 92965
15015 92965
44119 92965
78632 92965
8...

output:

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
...

result:

ok 300000 lines

Test #82:

score: 83
Accepted
time: 529ms
memory: 33628kb

input:

100000 199998
1195 89256
89256 88760
88760 1195
1195 9608
9608 88760
88760 99850
99850 89256
88760 16661
16661 1195
88760 81642
81642 99850
99850 77798
77798 9608
77798 83395
83395 88760
9608 32926
32926 99850
77798 38301
38301 16661
1195 53858
53858 88760
99850 48623
48623 38301
9608 17843
17843 48...

output:

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
...

result:

ok 199998 lines

Test #83:

score: 83
Accepted
time: 521ms
memory: 33600kb

input:

100000 199998
58991 2427
58991 17012
17012 2427
58991 78129
78129 17012
2427 88194
88194 78129
58991 15762
15762 88194
2427 53730
53730 78129
15762 32007
32007 2427
32007 72885
72885 88194
2427 98398
98398 78129
17012 55912
55912 98398
88194 65979
65979 58991
17012 4587
4587 15762
58991 69487
69487 ...

output:

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
...

result:

ok 199998 lines

Test #84:

score: 83
Accepted
time: 451ms
memory: 33644kb

input:

100000 199998
74925 40333
74925 90725
90725 40333
90725 26264
26264 74925
26264 36696
36696 74925
36696 75678
75678 90725
75678 69692
69692 40333
69692 97703
97703 36696
97703 16160
16160 74925
97703 49919
49919 16160
97703 93758
93758 49919
49919 45570
45570 93758
75678 72973
72973 45570
75678 4711...

output:

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
...

result:

ok 199998 lines

Test #85:

score: 83
Accepted
time: 457ms
memory: 33528kb

input:

100000 199998
72301 78177
78177 42728
42728 72301
42728 30400
30400 72301
30400 69985
69985 42728
69985 75538
75538 72301
69985 17536
17536 75538
17536 95369
95369 75538
69985 41396
41396 95369
17536 42471
42471 41396
42471 24427
24427 72301
24427 18690
18690 42728
18690 91876
91876 78177
91876 3119...

output:

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
...

result:

ok 199998 lines

Test #86:

score: 83
Accepted
time: 157ms
memory: 20836kb

input:

100000 199998
79003 28704
28704 79003
28447 11383
11383 28447
23543 72872
72872 23543
25755 27237
27237 25755
74001 50503
50503 74001
58915 3129
3129 58915
45925 18248
18248 45925
67587 83847
83847 67587
72103 24952
24952 72103
99152 90578
90578 99152
81140 6061
6061 81140
946 98687
98687 946
16520 ...

output:

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
...

result:

ok 199998 lines

Test #87:

score: 83
Accepted
time: 176ms
memory: 20812kb

input:

100000 300000
11146 49734
49734 11146
32586 30103
30103 32586
1599 212
212 1599
15498 23636
23636 15498
28702 22931
22931 28702
74869 58344
58344 74869
97021 30241
30241 97021
68386 56352
56352 68386
91000 28511
28511 91000
89950 20262
20262 89950
26676 64534
64534 26676
34139 5858
5858 34139
30184 ...

output:

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
...

result:

ok 300000 lines

Test #88:

score: 83
Accepted
time: 324ms
memory: 21892kb

input:

100000 199998
31366 62700
39507 63616
39264 72672
6302 23479
36942 73245
2176 94170
9431 3828
39852 66434
63103 71798
32559 19585
66894 87718
68945 84099
23555 52864
11635 76118
23504 39320
35915 74760
724 56812
79551 86207
29714 93855
76259 93962
93919 71571
4233 86275
60124 15202
61483 80569
96269...

output:

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
...

result:

ok 199998 lines

Test #89:

score: 83
Accepted
time: 504ms
memory: 28204kb

input:

100000 300000
4892 75676
12898 67058
95671 95306
37452 397
58820 53809
44195 76784
91204 90705
84716 38352
26913 51383
226 24546
69934 39690
78190 7849
9633 5963
16328 88230
99726 84940
82810 16445
1998 174
21633 84337
48359 61242
30458 20501
91479 21372
66318 90128
15302 66752
1742 88611
13611 3687...

output:

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
...

result:

ok 300000 lines

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

服务器时间: 2025-01-21 04:59:30 | 开源项目