QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#416269	#6340. Tourism	james1BadCreeper^#	28	3892ms	24252kb	C++17	2.7kb	2024-05-21 18:38:49	2024-05-21 18:38:50

Judging History

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

[2024-05-21 18:38:50]
评测

测评结果：28
用时：3892ms
内存：24252kb

查看

[2024-05-21 18:38:49]
提交

answer

#include <bits/stdc++.h>
using namespace std; 
const int N = 1e5 + 5; 
const int B = 400; 

int n, m, q, a[N], pos[N]; 
int mi[18][N], d[N]; 
vector<int> G[N]; 
int dfn[N], num, idx[N]; 

inline int get(int u, int v) { return dfn[u] < dfn[v] ? u : v; }
inline void dfs(int x, int fa) {
    mi[0][dfn[x] = ++num] = fa; d[x] = d[fa] + 1; idx[num] = x; 
    for (int y : G[x]) if (y != fa) dfs(y, x); 
}
inline int lca(int u, int v) {
    if (u == v) return u; 
    if ((u = dfn[u]) > (v = dfn[v])) swap(u, v); 
    int k = __lg(v - u++); 
    return get(mi[k][u], mi[k][v - (1 << k) + 1]); 
}
inline int dist(int u, int v) {
    u = idx[u]; v = idx[v]; 
    return d[u] + d[v] - 2 * d[lca(u, v)]; 
}

struct Query {
    int l, r, id; 
    bool operator< (const Query &a) const {
        if (pos[l] == pos[a.l]) return (pos[l] & 1 ? r < a.r : r > a.r); 
        return l < a.l; 
    }
} Q[N]; 
int ans[N], Ans, cnt[N]; 
set<int> s; 
inline auto Prev(auto it) {
    if (it == s.begin()) return prev(s.end()); 
    return prev(it); 
}
inline auto Next(auto it) {
    if (it == prev(s.end())) return s.begin(); 
    return next(it); 
}
inline void add(int x) {
    x = dfn[x]; 

    if (cnt[x]++) return; 

    auto it = s.insert(x).first; 
    
    if (s.size() >= 2) {
        int prv = *Prev(it), nxt = *Next(it); 
        if (s.size() >= 3) Ans -= dist(prv, nxt); 
        Ans += dist(x, nxt) + dist(prv, x); 
    }
}
inline void del(int x) {
    x = dfn[x]; cnt[x]--; 
    if (cnt[x] > 0) return; 
    auto it = s.find(x); 
    if (s.size() >= 2) {
        int prv = *Prev(it), nxt = *Next(it); 
        Ans -= dist(x, nxt) + dist(prv, x); 
        if (s.size() >= 3) Ans += dist(nxt, prv); 
    }
    s.erase(it); 
}

int main(void) {
    ios::sync_with_stdio(0); cin.tie(0); 

    cin >> n >> m >> q; 
    
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v; 
        G[u].emplace_back(v); G[v].emplace_back(u); 
    }

    dfs(1, 0); 

    for (int i = 1; i <= 17; ++i)
        for (int j = 1; j + (1 << i) - 1 <= n; ++j)
            mi[i][j] = get(mi[i - 1][j], mi[i - 1][j + (1 << i - 1)]); 
    
    for (int i = 1; i <= m; ++i) cin >> a[i], pos[i] = (i - 1) / B + 1; 

    for (int i = 1; i <= q; ++i) cin >> Q[i].l >> Q[i].r, Q[i].id = i; 

    sort(Q + 1, Q + q + 1); 

    for (int L = 1, R = 0, i = 1; i <= q; ++i) {

        while (R < Q[i].r) add(a[++R]); 
        while (L > Q[i].l) add(a[--L]); 
        while (R > Q[i].r) del(a[R--]); 
        while (L < Q[i].l) del(a[L++]); 
    
        ans[Q[i].id] = (Ans / 2 + 1); 
    }

    for (int i = 1; i <= q; ++i) cout << ans[i] << "\n"; 
    return 0; 
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5

Accepted

Test #1:

score: 5

Accepted

time: 3ms

memory: 11856kb

input:

166 249 224
158 52
52 82
158 36
117 158
119 117
5 82
158 18
22 36
82 143
105 36
22 152
36 92
117 2
123 158
5 134
119 89
31 119
92 48
105 149
149 17
108 31
134 50
3 52
63 158
3 51
42 22
17 10
103 158
50 122
92 85
50 78
117 159
36 20
143 115
158 83
20 4
142 22
23 3
96 10
19 134
8 10
151 92
65 108
89 5...

output:

result:

ok 224 numbers

Test #2:

score: 0

Accepted

time: 0ms

memory: 13884kb

input:

225 173 232
88 46
74 88
88 60
86 46
202 86
175 86
165 74
60 61
13 88
78 46
61 163
61 123
13 15
211 60
78 75
123 188
165 146
88 93
93 214
16 202
137 146
75 133
202 1
213 202
30 214
203 165
146 222
91 146
203 106
23 75
104 202
30 47
165 174
144 133
137 58
20 1
75 183
133 26
21 30
80 93
106 36
207 188
...

output:

result:

ok 232 numbers

Test #3:

score: 0

Accepted

time: 0ms

memory: 11832kb

input:

161 196 214
46 122
64 46
156 46
146 122
46 105
16 122
119 156
121 119
156 58
46 40
99 105
119 113
91 16
13 113
13 39
40 49
147 105
11 40
99 148
7 156
113 53
32 64
132 7
32 108
32 54
40 111
119 137
127 32
91 34
136 147
148 71
26 46
64 68
9 34
78 9
40 110
153 78
5 13
78 70
96 153
55 64
131 121
21 108
...

output:

result:

ok 214 numbers

Test #4:

score: 0

Accepted

time: 0ms

memory: 11804kb

input:

191 176 283
154 157
154 109
157 113
122 109
78 109
78 133
109 132
31 157
77 109
154 24
132 35
132 74
78 26
86 35
157 117
59 133
29 77
117 186
37 186
70 157
76 186
44 77
42 154
170 24
74 99
132 30
99 156
133 67
35 20
51 31
71 44
121 109
84 154
26 119
38 30
67 166
102 121
77 32
20 167
170 123
123 61
1...

output:

result:

ok 283 numbers

Test #5:

score: 0

Accepted

time: 0ms

memory: 15924kb

input:

280 195 170
153 16
153 152
249 153
152 87
210 152
111 210
11 152
75 111
247 249
155 16
142 111
152 125
155 241
210 23
93 241
142 108
11 15
249 183
183 131
38 23
142 271
34 183
75 225
80 93
247 85
153 136
41 249
38 91
15 43
158 153
144 271
96 93
131 232
11 116
131 68
75 188
179 225
99 75
87 250
41 14...

output:

result:

ok 170 numbers

Test #6:

score: 0

Accepted

time: 0ms

memory: 11856kb

input:

300 300 300
9 290
290 177
9 57
258 290
115 57
177 116
57 48
177 113
177 151
290 105
285 57
154 48
154 300
251 57
300 217
154 267
127 115
48 275
154 287
38 177
9 253
285 86
34 275
199 300
115 183
178 115
57 70
251 110
127 43
26 9
165 86
257 105
59 127
115 66
252 183
86 92
281 285
7 127
59 179
245 183...

output:

result:

ok 300 numbers

Test #7:

score: 0

Accepted

time: 4ms

memory: 11940kb

input:

300 300 300
69 94
5 94
287 5
94 289
13 5
5 159
226 159
148 94
69 191
116 148
94 57
57 24
98 69
115 24
226 271
77 57
67 271
158 69
252 69
158 37
69 121
244 287
139 77
91 139
238 287
91 154
77 9
278 115
139 221
203 158
37 127
159 292
177 148
69 174
279 244
40 221
98 260
268 69
158 12
144 40
244 213
27...

output:

result:

ok 300 numbers

Test #8:

score: 0

Accepted

time: 0ms

memory: 11856kb

input:

300 300 300
230 57
57 140
227 230
227 164
57 199
49 57
49 131
57 208
98 57
281 98
131 76
103 227
49 46
279 140
279 83
295 49
24 131
78 279
127 24
281 9
199 104
230 256
122 103
111 49
176 256
57 119
83 135
131 273
279 206
176 278
83 211
256 193
211 259
21 199
257 9
194 127
269 295
257 298
131 129
206...

output:

result:

ok 300 numbers

Test #9:

score: 0

Accepted

time: 0ms

memory: 13988kb

input:

300 300 300
275 44
19 44
184 275
8 184
8 68
274 44
184 257
19 154
227 154
44 84
23 227
256 84
154 31
160 8
100 160
273 100
154 77
100 150
121 8
273 50
218 121
201 150
77 266
202 201
31 131
23 261
65 8
47 160
123 218
164 100
202 15
50 259
274 182
196 31
98 150
202 113
164 59
83 68
261 177
116 275
261...

output:

result:

ok 300 numbers

Test #10:

score: 0

Accepted

time: 2ms

memory: 13972kb

input:

300 300 300
151 108
151 217
71 217
64 71
108 86
151 285
86 12
71 101
281 151
134 71
148 86
217 179
131 86
229 148
12 190
274 101
89 12
286 190
12 232
43 232
172 148
229 140
108 208
64 249
151 169
84 86
134 115
131 82
58 229
71 98
86 163
169 248
115 127
274 70
163 51
172 287
153 287
44 208
281 291
93...

output:

result:

ok 300 numbers

Test #11:

score: 0

Accepted

time: 0ms

memory: 11908kb

input:

300 300 300
210 194
210 179
46 210
46 186
256 179
56 256
46 44
194 192
106 179
56 146
17 194
179 197
23 17
106 121
257 194
23 160
23 124
257 48
179 71
187 160
179 35
186 252
197 195
43 35
35 278
248 278
13 35
15 13
278 272
199 257
252 244
195 9
164 13
17 147
214 257
155 278
82 56
263 43
172 48
28 24...

output:

result:

ok 300 numbers

Test #12:

score: 0

Accepted

time: 4ms

memory: 11868kb

input:

300 300 300
96 198
70 96
167 70
273 167
273 52
52 204
63 204
143 63
296 143
296 92
292 92
17 292
17 166
166 290
290 66
66 105
80 105
80 51
277 51
277 168
223 168
223 152
152 54
116 54
177 116
177 186
190 186
190 68
101 68
101 182
300 182
300 213
110 213
110 179
179 205
205 119
33 119
33 65
147 65
25...

output:

result:

ok 300 numbers

Test #13:

score: 0

Accepted

time: 0ms

memory: 11912kb

input:

300 300 300
15 60
15 287
26 287
3 26
3 145
177 145
177 122
29 122
29 75
198 75
31 198
31 172
219 172
126 219
126 84
56 84
56 203
203 225
227 225
227 195
200 195
217 200
47 217
47 73
251 73
118 251
118 14
42 14
263 42
7 263
32 7
102 32
102 205
205 64
253 64
253 120
120 166
166 164
185 164
185 254
254...

output:

result:

ok 300 numbers

Test #14:

score: 0

Accepted

time: 4ms

memory: 13956kb

input:

300 300 300
145 236
290 145
290 3
136 3
135 136
135 284
284 45
45 62
12 62
265 12
265 154
154 226
273 226
256 273
256 30
30 137
259 137
251 259
251 72
218 72
218 73
188 73
168 188
168 158
158 214
214 152
152 37
37 268
227 268
227 206
206 95
53 95
53 127
90 127
213 90
213 74
74 164
149 164
94 149
94 ...

output:

result:

ok 300 numbers

Test #15:

score: 0

Accepted

time: 0ms

memory: 11936kb

input:

300 300 300
124 163
292 163
292 197
208 197
271 208
271 261
261 144
144 153
153 139
139 213
279 213
279 50
15 50
297 15
143 297
143 45
146 45
232 146
169 232
169 265
221 265
221 136
225 136
6 225
164 6
296 164
11 296
11 95
27 95
61 27
114 61
295 114
295 184
41 184
143 78
78 43
42 43
42 244
21 244
74...

output:

result:

ok 300 numbers

Test #16:

score: 0

Accepted

time: 3ms

memory: 11936kb

input:

300 300 300
164 241
156 164
156 37
37 173
173 29
29 291
291 129
275 129
118 275
254 118
254 217
217 210
210 271
271 139
160 139
181 160
211 181
211 99
74 99
208 74
208 123
123 202
214 202
80 214
121 80
121 263
263 8
8 22
6 22
149 6
149 295
285 295
94 285
140 94
140 104
104 230
183 230
183 87
62 87
4...

output:

result:

ok 300 numbers

Test #17:

score: 0

Accepted

time: 4ms

memory: 13892kb

input:

300 300 300
152 232
247 232
247 75
75 56
56 50
256 75
160 256
260 160
28 260
28 40
40 269
146 269
146 35
35 117
117 235
230 235
126 230
126 201
43 201
43 93
282 93
171 282
171 194
194 270
270 89
76 89
76 224
224 181
288 181
291 288
291 95
293 95
105 293
105 298
298 262
262 217
217 13
13 139
139 73
7...

output:

result:

ok 300 numbers

Test #18:

score: 0

Accepted

time: 0ms

memory: 11944kb

input:

300 300 300
31 202
254 31
227 31
31 247
31 5
2 31
272 31
68 31
31 151
98 31
31 183
207 31
31 193
189 31
31 173
31 89
248 31
31 156
258 31
157 31
31 106
31 234
31 139
127 31
31 50
31 256
162 31
199 31
31 67
31 62
31 165
31 138
132 31
31 46
120 31
229 31
31 171
241 31
192 31
42 31
31 48
198 31
31 94
7...

output:

result:

ok 300 numbers

Test #19:

score: 0

Accepted

time: 0ms

memory: 11924kb

input:

300 300 300
116 172
100 172
172 251
172 266
172 173
64 172
276 172
172 60
172 204
293 172
27 172
153 172
172 82
172 244
220 172
297 172
172 189
97 172
172 168
125 172
172 179
172 232
172 227
28 172
288 172
172 195
172 48
25 172
172 119
172 226
172 250
172 46
172 182
172 165
172 93
280 172
172 258
17...

output:

result:

ok 300 numbers

Test #20:

score: 0

Accepted

time: 3ms

memory: 11864kb

input:

300 300 300
98 64
98 292
98 105
98 32
98 196
276 98
4 98
12 98
150 98
27 98
73 98
256 98
124 98
98 237
98 202
98 133
98 239
98 3
98 190
273 98
98 20
295 98
182 98
98 226
98 177
253 98
98 266
51 98
98 63
238 98
19 98
98 218
156 98
103 98
98 146
274 98
112 98
98 251
98 86
50 98
184 98
186 98
92 98
98 ...

output:

result:

ok 300 numbers

Test #21:

score: 0

Accepted

time: 3ms

memory: 11864kb

input:

300 300 300
109 116
116 230
116 158
96 116
116 272
116 218
158 160
116 234
116 32
185 116
116 266
210 116
65 116
47 116
56 116
116 55
78 116
286 116
197 116
116 83
116 25
116 44
116 231
139 116
205 116
12 116
116 4
277 116
116 247
116 104
204 116
215 116
269 116
118 116
90 116
116 292
116 51
116 98
...

output:

result:

ok 300 numbers

Test #22:

score: 0

Accepted

time: 3ms

memory: 11980kb

input:

300 300 300
203 253
245 203
4 203
203 38
197 203
203 144
202 203
243 203
291 203
10 203
281 203
203 123
88 203
203 90
203 225
238 203
115 203
221 203
203 289
195 203
203 91
25 203
203 294
191 203
203 116
92 203
122 203
203 138
203 149
32 203
203 74
203 135
137 203
203 22
76 203
203 177
100 203
203 1...

output:

result:

ok 300 numbers

Test #23:

score: 0

Accepted

time: 0ms

memory: 11988kb

input:

300 300 300
122 269
269 21
171 269
269 221
132 269
269 161
232 269
126 269
269 237
269 157
269 190
79 269
269 43
289 269
269 234
80 269
127 269
269 163
269 68
269 188
269 274
269 175
269 49
269 252
269 143
269 147
269 230
269 138
300 269
269 98
105 269
116 269
165 269
258 269
269 113
269 131
269 201...

output:

result:

ok 300 numbers

Test #24:

score: 0

Accepted

time: 0ms

memory: 11864kb

input:

1 300 300
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

result:

ok 300 numbers

Test #25:

score: 0

Accepted

time: 0ms

memory: 13976kb

input:

output:

result:

ok 300 numbers

Test #26:

score: 0

Accepted

time: 2ms

memory: 11980kb

input:

300 300 300
290 253
290 246
253 35
35 148
27 290
35 141
253 90
187 290
253 259
27 59
119 187
290 192
141 174
59 54
222 59
27 161
270 161
32 35
32 111
270 185
90 24
24 190
241 253
270 95
45 141
241 83
107 35
95 208
269 148
246 99
231 83
45 296
95 78
253 136
241 152
40 83
116 269
95 211
118 107
241 49...

output:

result:

ok 300 numbers

Subtask #2:

score: 5

Accepted

Dependency #1:

100%

Accepted

Test #27:

score: 5

Accepted

time: 6ms

memory: 11964kb

input:

1473 1453 1340
1202 996
996 681
720 996
720 1382
132 996
789 681
1024 1202
261 789
1133 1382
420 996
1133 603
1382 1461
1470 1202
1470 708
313 1461
788 720
132 710
1153 681
11 1133
710 221
681 88
925 1133
720 494
682 789
107 788
1164 261
1024 893
1133 163
868 11
1164 726
868 604
1212 88
420 1172
138...

output:

result:

ok 1340 numbers

Test #28:

score: 0

Accepted

time: 13ms

memory: 16112kb

input:

1437 1592 1756
1289 660
454 1289
1289 847
660 1069
803 847
721 660
660 1043
1069 1337
1253 1337
454 462
1289 768
721 911
638 847
1043 54
261 638
153 721
54 1194
1289 637
1339 660
1043 216
54 1351
1312 721
1043 679
138 1253
880 1351
196 911
196 155
1395 54
153 1273
216 1136
637 732
1395 557
1046 462
...

output:

result:

ok 1756 numbers

Test #29:

score: 0

Accepted

time: 19ms

memory: 12132kb

input:

2000 2000 2000
1144 879
1144 841
1037 841
673 1144
641 879
673 142
1037 1494
673 1920
1094 1920
879 1093
1037 1796
1745 1093
1745 1455
497 1093
68 1094
1225 1745
317 641
1494 582
1920 605
1444 497
1008 1796
582 470
300 1225
1015 1745
737 497
879 1145
1494 608
219 1094
1035 300
1444 892
673 1932
1032...

output:

result:

ok 2000 numbers

Test #30:

score: 0

Accepted

time: 15ms

memory: 12068kb

input:

2000 2000 2000
722 1697
755 722
1697 290
300 755
1828 755
290 969
365 722
1394 755
969 1549
10 1697
1601 969
1108 1601
300 1398
300 1408
1108 1351
1697 1883
593 10
66 1108
1207 1697
110 1697
593 444
1983 66
36 1883
1351 1847
1540 1351
1398 289
1697 1214
871 1351
558 1883
256 300
1314 558
1547 1601
1...

output:

result:

ok 2000 numbers

Test #31:

score: 0

Accepted

time: 15ms

memory: 12012kb

input:

2000 2000 2000
1414 105
1648 1414
105 1324
1324 1634
5 1648
1324 800
1878 5
1438 1324
1505 1634
1615 1438
1505 1495
1615 533
1414 726
1432 1505
1414 192
1648 1819
1648 1489
667 800
1505 1756
1796 800
481 1634
5 1223
245 105
1819 1427
1634 1962
1962 1603
760 1603
1615 157
327 1223
1819 1861
192 672
3...

output:

result:

ok 2000 numbers

Test #32:

score: 0

Accepted

time: 0ms

memory: 16180kb

input:

2000 2000 2000
1381 1760
719 1381
719 199
1802 199
1381 709
1381 29
80 1802
199 1209
709 1221
1405 1760
1381 1954
1437 1209
1777 719
1190 709
29 1859
719 1862
1190 1206
880 199
199 1792
874 1760
56 80
1190 519
29 570
719 428
1867 1954
80 1876
668 1437
880 1814
760 80
1229 1760
1229 1884
1198 56
1862...

output:

result:

ok 2000 numbers

Test #33:

score: 0

Accepted

time: 4ms

memory: 12088kb

input:

2000 2000 2000
1405 1156
1156 254
1107 1405
1107 1102
1156 1745
1107 1210
1431 1745
1102 978
357 1431
1405 1782
396 1431
357 1696
357 1013
1431 545
1259 357
1107 32
1009 545
1564 1210
32 481
1009 1930
325 254
483 1696
1629 254
1867 1782
1782 1702
189 32
1405 664
1696 1404
1013 1139
1210 1487
1702 19...

output:

result:

ok 2000 numbers

Test #34:

score: 0

Accepted

time: 4ms

memory: 12092kb

input:

2000 2000 2000
722 1610
800 722
800 1902
1146 1610
722 263
1960 1610
1420 1902
1902 1634
1610 1181
479 1634
800 1203
291 1610
722 408
291 718
1420 94
408 821
1610 629
408 1051
94 1171
1420 207
479 1631
777 1610
408 191
408 838
800 1427
1865 1902
1493 1146
718 1549
727 191
1224 1631
207 1394
88 94
28...

output:

result:

ok 2000 numbers

Test #35:

score: 0

Accepted

time: 20ms

memory: 12160kb

input:

2000 2000 2000
919 1147
1802 919
1802 199
199 1712
884 1712
884 935
935 1296
743 1296
1140 743
1140 1360
1360 230
230 70
70 1393
1393 885
885 1342
1342 1838
856 1838
856 1942
1942 1188
1188 851
1449 851
15 1449
15 1017
1017 185
185 1031
203 1031
203 100
354 100
354 545
545 1772
1772 1094
1094 1495
1...

output:

result:

ok 2000 numbers

Test #36:

score: 0

Accepted

time: 17ms

memory: 16172kb

input:

2000 2000 2000
820 1043
820 1055
1055 1094
1094 905
905 550
550 1650
1312 1650
1312 1143
1143 1121
1121 1346
1346 734
45 734
45 1553
1262 1553
1871 1262
346 1871
346 278
249 278
795 249
427 795
519 427
973 519
973 1538
1538 1111
532 1111
532 1024
802 1024
802 1101
29 1101
29 1170
1170 1153
1153 1938...

output:

result:

ok 2000 numbers

Test #37:

score: 0

Accepted

time: 16ms

memory: 14108kb

input:

2000 2000 2000
1987 1006
962 1006
1936 962
1936 1905
1905 134
134 1420
648 1420
460 648
460 1434
1434 783
1440 783
1198 1440
1198 1967
1967 216
1266 216
1266 825
1862 825
1862 264
1212 264
993 1212
993 408
966 408
966 1117
428 1117
428 1623
1824 1623
1970 1824
551 1970
1566 551
1566 1565
1054 1565
1...

output:

result:

ok 2000 numbers

Test #38:

score: 0

Accepted

time: 4ms

memory: 14112kb

input:

2000 2000 2000
1791 1481
1347 1791
1347 1772
1875 1772
249 1875
249 144
144 1375
1375 293
1586 293
732 1586
732 996
996 1562
1915 1562
1915 729
729 1862
1862 330
830 330
599 830
340 599
1836 340
1836 386
113 386
1864 113
983 1864
983 1397
1397 200
200 15
516 15
1405 516
1405 875
875 73
513 73
1222 5...

output:

result:

ok 2000 numbers

Test #39:

score: 0

Accepted

time: 0ms

memory: 12148kb

input:

2000 2000 2000
1080 1228
1228 329
1380 329
1569 1380
1814 1569
1814 1368
1368 1267
1267 1076
1253 1076
59 1253
47 59
47 811
811 871
871 805
494 805
105 494
518 105
518 1345
1345 1105
374 1105
1260 374
1260 96
606 96
727 606
1595 727
1305 1595
1305 1457
1457 1739
314 1739
1336 314
1336 1500
1206 1500...

output:

result:

ok 2000 numbers

Test #40:

score: 0

Accepted

time: 3ms

memory: 12036kb

input:

2000 2000 2000
543 17
543 1251
1182 1251
271 1182
271 1964
363 1964
363 1894
1894 1131
1383 1131
1383 1704
1704 1081
1081 875
875 909
909 610
36 610
381 36
381 1885
1885 301
301 1101
1101 865
1835 865
544 1835
544 702
1757 702
688 1757
688 1578
1578 1227
1227 1050
1050 585
585 1549
1127 1549
1127 70...

output:

result:

ok 2000 numbers

Test #41:

score: 0

Accepted

time: 16ms

memory: 12028kb

input:

2000 2000 2000
453 1834
453 1838
1081 1838
1081 1052
1052 45
45 1894
1631 1894
1631 91
1857 91
1857 294
899 294
372 899
1039 372
977 1039
1457 977
1898 1457
1898 988
1373 988
1413 1373
1227 1413
747 1227
1957 747
1945 1957
1339 1945
1339 249
249 1703
1703 1642
1642 985
6 985
988 1118
1118 403
403 18...

output:

result:

ok 2000 numbers

Test #42:

score: 0

Accepted

time: 21ms

memory: 14084kb

input:

2000 2000 2000
1869 445
1365 1869
1206 1365
1206 384
1989 384
1989 1733
1733 1793
502 1793
967 502
569 967
569 649
937 649
564 937
564 743
95 743
1274 95
1594 1274
1594 126
1068 126
877 1068
877 488
1220 488
1220 236
989 236
989 1261
1261 862
1343 862
1343 1557
354 1557
1293 354
1012 1293
1012 1016
...

output:

result:

ok 2000 numbers

Test #43:

score: 0

Accepted

time: 18ms

memory: 16152kb

input:

2000 2000 2000
1730 1659
1646 1730
1646 374
374 432
1579 432
1579 1327
1327 662
1287 662
613 1287
762 613
762 1166
521 1166
1945 521
1945 626
626 1390
1390 1261
577 1261
577 19
19 773
1958 773
1017 1958
1624 1017
1624 671
1218 671
1622 1218
1622 604
1220 604
1220 1396
1306 1396
1306 1746
1746 67
195...

output:

result:

ok 2000 numbers

Test #44:

score: 0

Accepted

time: 4ms

memory: 14084kb

input:

2000 2000 2000
805 611
805 436
1789 436
126 1789
126 1758
1758 464
464 727
1163 727
1439 1163
1439 1115
1115 1621
1621 746
967 746
967 58
58 1258
1481 1258
1481 74
1302 74
1302 1999
1999 442
442 1418
1418 987
602 987
602 705
705 1109
1019 1109
434 1019
124 434
124 1365
811 1365
782 811
1381 782
505 ...

output:

result:

ok 2000 numbers

Test #45:

score: 0

Accepted

time: 4ms

memory: 12092kb

input:

2000 2000 2000
741 677
677 96
1467 96
480 96
1118 480
988 1118
1197 988
514 1197
514 706
217 706
217 416
416 708
1134 708
244 1134
244 327
1668 327
7 1668
7 1424
1424 221
221 1280
1999 1280
1125 1999
1125 492
492 1371
1371 1748
1748 1715
437 1715
996 437
1289 996
417 1289
417 228
1753 228
1753 325
4...

output:

result:

ok 2000 numbers

Test #46:

score: 0

Accepted

time: 4ms

memory: 14200kb

input:

2000 2000 2000
1187 524
1187 43
154 43
522 154
569 522
569 767
384 767
384 115
115 1948
1948 536
960 536
960 763
763 1237
243 1237
1725 243
1725 326
326 508
787 508
291 787
291 1674
242 1674
242 953
1074 953
1074 621
621 1739
1739 1257
1257 1655
1603 1655
1574 1603
1574 1621
1399 1621
1399 717
1191 ...

output:

result:

ok 2000 numbers

Test #47:

score: 0

Accepted

time: 19ms

memory: 14144kb

input:

2000 2000 2000
152 1328
1135 1328
1335 1328
438 1328
1328 1123
1846 1328
1328 381
1328 760
1328 649
1355 1328
1328 712
1298 1328
107 1328
1328 191
7 1328
1328 9
1536 1328
1328 1664
1328 1456
1328 815
1229 1328
1328 915
1328 1946
1328 1825
1662 1328
1343 1328
1328 187
214 1328
399 1328
803 1328
1328 ...

output:

result:

ok 2000 numbers

Test #48:

score: 0

Accepted

time: 17ms

memory: 12100kb

input:

2000 2000 2000
406 160
1111 160
160 1599
436 160
160 1169
1548 160
395 160
160 1434
11 160
160 1407
160 425
1990 160
1757 160
732 160
160 1078
160 66
160 162
160 1544
160 1940
993 160
160 606
160 98
1496 160
160 716
160 1092
160 1395
920 160
531 160
884 160
160 680
160 1747
1658 160
160 1705
40 160
...

output:

result:

ok 2000 numbers

Test #49:

score: 0

Accepted

time: 18ms

memory: 14080kb

input:

2000 2000 2000
1460 594
1854 594
1462 594
1973 594
1763 594
1125 594
594 1463
594 88
594 737
594 901
594 1837
594 236
1170 594
594 1738
594 1518
1129 594
779 594
594 714
594 1145
594 843
1665 594
269 594
594 1022
594 1959
594 1237
504 594
1851 594
1827 594
1132 594
594 1966
9 594
140 594
594 260
984...

output:

result:

ok 2000 numbers

Test #50:

score: 0

Accepted

time: 15ms

memory: 14068kb

input:

2000 2000 2000
1856 387
1063 387
1932 387
295 387
96 387
387 1334
1651 387
1872 387
387 61
387 1639
387 1523
387 1292
948 387
387 1606
1875 387
1779 387
1670 387
667 387
699 387
387 309
387 1041
387 879
387 918
1285 387
387 539
1540 387
387 1050
387 16
671 387
1962 387
853 387
387 1745
387 768
409 3...

output:

result:

ok 2000 numbers

Test #51:

score: 0

Accepted

time: 15ms

memory: 16068kb

input:

2000 2000 2000
1743 425
425 1015
425 1426
599 425
1226 425
425 1448
425 1441
425 111
425 1833
49 425
425 1190
425 1285
1007 425
1949 425
1424 425
160 425
425 1941
425 82
357 425
974 425
425 52
1967 425
180 425
425 53
451 425
1942 425
425 89
1427 425
425 1804
1249 425
425 433
343 425
410 425
662 425
...

output:

result:

ok 2000 numbers

Test #52:

score: 0

Accepted

time: 19ms

memory: 14064kb

input:

2000 2000 2000
1222 764
1236 764
764 905
764 161
764 245
764 1051
1375 764
764 580
764 506
340 764
1846 764
909 764
764 117
32 764
220 764
1704 764
764 1815
764 872
764 1981
1763 764
764 1032
944 764
628 764
764 1570
764 1784
764 1447
764 1808
1013 764
764 147
764 177
764 1397
1297 764
137 764
764 1...

output:

result:

ok 2000 numbers

Test #53:

score: 0

Accepted

time: 0ms

memory: 9896kb

input:

1 2000 2000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

result:

ok 2000 numbers

Test #54:

score: 0

Accepted

time: 0ms

memory: 15992kb

input:

2000 1 2000
1831 109
303 1831
303 203
1531 303
883 1831
372 1831
1583 883
1757 109
429 1583
636 883
372 1365
303 1579
1531 1069
1831 139
1764 1757
1831 98
1177 1579
861 303
1757 1442
889 372
372 843
1757 873
873 1439
1764 1276
203 212
1276 1421
1069 1939
372 1192
1032 636
1569 139
590 1421
73 873
13...

output:

result:

ok 2000 numbers

Test #55:

score: 0

Accepted

time: 0ms

memory: 12032kb

input:

2000 2000 2000
380 12
380 842
380 1917
412 12
542 12
245 12
842 1941
1941 1987
1941 1458
378 542
245 1136
1987 704
289 1136
1833 542
704 865
865 1746
701 12
1652 12
412 702
922 1746
1440 702
420 542
1941 121
1652 876
245 1831
484 1917
1917 36
36 843
1652 1389
704 324
1097 1652
1178 412
344 1746
158 ...

output:

result:

ok 2000 numbers

Subtask #3:

score: 0

Time Limit Exceeded

Test #56:

score: 7

Accepted

time: 2504ms

memory: 21004kb

input:

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

output:

result:

ok 75523 numbers

Test #57:

score: 0

Accepted

time: 1798ms

memory: 22464kb

input:

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

output:

result:

ok 65576 numbers

Test #58:

score: 0

Accepted

time: 2611ms

memory: 24252kb

input:

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

output:

result:

ok 54619 numbers

Test #59:

score: -7

Time Limit Exceeded

input:

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

output:

result:

Subtask #4:

score: 18

Accepted

Test #69:

score: 18

Accepted

time: 42ms

memory: 16396kb

input:

54738 54525 1797
45211 4527
4527 43609
4527 19876
16325 43609
32183 4527
16325 32579
43609 25554
32183 38972
45211 53953
16325 19810
10881 19810
45211 12698
27967 19810
25554 46338
51894 45211
25388 16325
512 25554
43609 7820
10206 512
30021 32183
48647 43609
46338 44138
16766 7820
10023 53953
19810...

output:

result:

ok 1797 numbers

Test #70:

score: 0

Accepted

time: 58ms

memory: 17012kb

input:

59284 89368 1930
4029 716
1741 4029
14542 4029
48937 4029
716 24494
29506 1741
4029 3097
2898 716
3097 8627
2898 46025
29506 15319
716 12015
1741 5566
8627 58178
2898 14837
7742 1741
21507 24494
20151 24494
48937 9926
55162 7742
32033 14837
2898 27435
12292 8627
24972 58178
55074 48937
45787 21507
1...

output:

result:

ok 1930 numbers

Test #71:

score: 0

Accepted

time: 50ms

memory: 16984kb

input:

67606 66951 1824
37697 58269
58269 20521
53476 37697
51085 20521
20521 3727
3727 59823
38837 53476
38837 40963
20521 28388
43757 51085
14394 58269
43757 1117
53476 60607
58269 57399
31600 57399
52004 3727
53476 44312
44312 49253
58269 2843
16982 43757
16982 60419
14394 5307
21031 20521
16982 13147
5...

output:

result:

ok 1824 numbers

Test #72:

score: 0

Accepted

time: 46ms

memory: 21764kb

input:

100000 100000 1
26451 75404
81327 75404
26451 29978
26451 40155
89550 29978
26451 16783
40584 40155
45697 16783
45697 46663
23828 46663
29978 77426
76408 26451
46663 8400
70202 29978
49633 40584
70202 77511
89375 76408
15804 29978
49633 38747
89550 42375
89550 81055
75404 88488
41733 89550
70202 137...

output:

result:

ok 1 number(s): "78872"

Test #73:

score: 0

Accepted

time: 63ms

memory: 20632kb

input:

100000 100000 3
82208 40540
80548 82208
51536 80548
80548 84376
93726 82208
16865 84376
40540 39439
35540 93726
94810 16865
58036 35540
41837 80548
41837 5186
48275 41837
81090 93726
13718 35540
16865 77
39439 33192
58036 56787
40540 21934
13718 41327
46616 16865
77 88013
98749 40540
33949 16865
460...

output:

50026
49745
49971

result:

ok 3 number(s): "50026 49745 49971"

Test #74:

score: 0

Accepted

time: 59ms

memory: 19436kb

input:

100000 100000 10
34595 88812
53602 88812
51012 88812
34595 25192
96336 34595
25192 61224
21676 25192
34595 84305
25192 87097
87097 78572
78572 56128
76900 56128
47761 88812
99770 61224
47761 12554
56128 58321
63156 58321
58321 9825
12554 15673
99770 81857
63156 29843
81905 88812
38032 34595
96336 36...

output:

result:

ok 10 numbers

Test #75:

score: 0

Accepted

time: 51ms

memory: 18664kb

input:

100000 100000 30
42863 76067
63251 42863
76067 48333
42863 53221
29390 42863
85971 42863
3185 42863
63251 42450
3185 19834
19834 44010
48470 42450
19834 22824
54068 85971
63251 65339
97059 44010
42450 66115
98472 97059
33557 42863
74927 54068
69415 42450
69415 3326
63251 41552
85971 67253
93346 5406...

output:

result:

ok 30 numbers

Test #76:

score: 0

Accepted

time: 52ms

memory: 19804kb

input:

100000 100000 100
22634 75465
19501 75465
25894 19501
14338 19501
5523 25894
52399 14338
52399 42507
67866 75465
25894 61608
25894 93402
87416 22634
45236 52399
36472 75465
61608 41436
92396 93402
85899 25894
41436 21440
14228 14338
85899 56625
83318 41436
21440 51711
6339 56625
51711 80000
36472 53...

output:

result:

ok 100 numbers

Test #77:

score: 0

Accepted

time: 55ms

memory: 18700kb

input:

100000 100000 300
90578 89684
89684 3831
90578 66618
77524 66618
90578 48241
57189 3831
64968 57189
69650 3831
25557 77524
86156 66618
90578 34093
16791 89684
85977 34093
8297 85977
57189 60674
89684 75021
75021 49529
14470 34093
75021 13628
64968 23217
49529 13292
13292 9531
86156 64479
95832 89684...

output:

result:

ok 300 numbers

Test #78:

score: 0

Accepted

time: 70ms

memory: 19816kb

input:

100000 100000 1000
39153 45943
94392 39153
79053 39153
94392 33885
2756 79053
51903 33885
38859 51903
79053 36974
2767 36974
2756 15571
36974 72001
15933 79053
15933 74976
51127 45943
19196 38859
12936 2756
25536 38859
79053 97016
39585 15571
56150 12936
44998 39153
80397 79053
2767 37989
32196 7905...

output:

result:

ok 1000 numbers

Test #79:

score: 0

Accepted

time: 71ms

memory: 18684kb

input:

100000 100000 3000
24460 92288
92288 78218
92288 90483
92288 23779
23145 78218
23145 86709
78006 86709
19093 92288
23145 15895
78006 10663
15895 19595
24460 29358
51460 19093
19093 96262
24460 64190
15895 91390
15895 22891
56695 78006
78218 81580
99267 91390
47670 19093
96262 46523
81580 62720
55665...

output:

result:

ok 3000 numbers

Test #80:

score: 0

Accepted

time: 73ms

memory: 18752kb

input:

100000 100000 10000
60471 67901
60471 79481
67901 70274
43259 60471
40484 60471
70274 91612
70274 95567
30745 70274
25482 40484
67901 68399
68978 79481
57690 79481
61927 95567
31670 67901
99069 30745
58593 99069
29956 79481
106 67901
43259 74994
40484 4306
40484 59011
62413 4306
59011 81345
31670 52...

output:

result:

ok 10000 numbers

Test #81:

score: 0

Accepted

time: 68ms

memory: 19888kb

input:

100000 100000 30000
16121 88102
71932 16121
88102 80368
80368 5806
88102 81591
80368 40177
45878 80368
16121 31693
81591 12812
21604 40177
60700 80368
32826 31693
8722 16121
40177 32445
13848 80368
20181 13848
20117 71932
32445 29712
80368 52542
80368 67199
88102 39197
36959 20181
86947 21604
60700 ...

output:

result:

ok 30000 numbers

Test #82:

score: 0

Accepted

time: 76ms

memory: 19676kb

input:

100000 100000 100000
25295 36699
36699 80196
25295 91969
86535 91969
94878 25295
80196 83806
94878 47722
36699 90327
8122 25295
90327 30030
91969 69857
17424 25295
99511 36699
86535 42411
91914 99511
43550 8122
13876 43550
47722 90714
90714 29235
90327 94216
16261 29235
86535 2183
13876 36794
33029 ...

output:

result:

ok 100000 numbers

Test #83:

score: 0

Accepted

time: 69ms

memory: 21628kb

input:

100000 100000 10000
38222 15170
15170 75637
99084 15170
80452 38222
15170 541
5526 80452
23574 80452
16220 15170
37892 5526
38222 27074
75637 97632
99084 76474
31858 5526
76474 91316
15170 4855
35230 541
99084 90246
35230 82033
37892 83347
25670 31858
80452 5212
81318 16220
27074 48624
56864 37892
4...

output:

result:

ok 10000 numbers

Test #84:

score: 0

Accepted

time: 71ms

memory: 20432kb

input:

100000 100000 10000
10087 59488
52461 59488
10087 45159
35663 52461
27244 10087
6802 10087
22085 45159
66718 52461
90682 59488
24586 22085
10087 47842
66718 32472
52461 19963
66718 48379
16667 35663
55150 59488
59488 71116
43492 55150
59488 50117
35663 44933
90682 58523
39987 32472
43492 53557
53557...

output:

result:

ok 10000 numbers

Test #85:

score: 0

Accepted

time: 76ms

memory: 20560kb

input:

100000 100000 10000
50249 81030
81030 77615
37533 50249
77615 71106
50249 66355
68757 77615
23692 77615
59517 71106
71106 43631
69947 43631
59081 71106
43631 99849
68757 87248
80348 81030
86928 71106
37533 49237
72424 77615
69925 69947
77615 94960
52230 99849
81030 97500
94960 40587
69925 90591
5223...

output:

result:

ok 10000 numbers

Test #86:

score: 0

Accepted

time: 48ms

memory: 21492kb

input:

100000 100000 1
17336 24713
8334 24713
3279 8334
3279 25340
99746 25340
27914 99746
27914 14041
14041 78218
15946 78218
70589 15946
70589 94215
80626 94215
77426 80626
77426 4928
42781 4928
42781 38468
764 38468
764 40711
78246 40711
61110 78246
89319 61110
29300 89319
20450 29300
60532 20450
60532 ...

output:

result:

ok 1 number(s): "99429"

Test #87:

score: 0

Accepted

time: 55ms

memory: 21436kb

input:

100000 100000 2
30969 34798
34798 58343
58343 81155
49294 81155
49294 33410
97390 33410
97390 81957
81957 3357
3357 40951
40951 31951
31951 96562
23439 96562
23439 88382
38083 88382
38083 26581
26581 55969
55969 16351
78107 16351
4882 78107
58029 4882
58029 9913
91908 9913
91908 11742
11742 69178
97...

output:

98472
98448

result:

ok 2 number(s): "98472 98448"

Test #88:

score: 0

Accepted

time: 69ms

memory: 19812kb

input:

100000 100000 5
75776 27
75776 83410
75192 83410
32454 75192
86642 32454
75192 23868
5657 23868
89968 5657
39947 89968
39947 89884
24021 89884
90531 24021
41514 90531
41514 86252
86252 33736
33736 97107
99170 97107
99170 25340
58761 25340
58761 84492
71696 83410
71696 15721
56118 15721
56118 88270
8...

output:

result:

ok 5 number(s): "95964 95972 95915 95902 95937"

Test #89:

score: 0

Accepted

time: 71ms

memory: 19148kb

input:

100000 100000 10
49590 51200
51200 92734
92734 62448
61295 62448
47940 61295
62140 47940
62140 19454
19454 56398
55020 56398
46127 55020
75883 46127
75883 90396
90396 36081
88892 36081
88892 80541
80541 74268
74268 60884
42690 60884
8388 42690
8388 69797
39651 69797
14311 39651
14311 92970
68505 929...

output:

result:

ok 10 numbers

Test #90:

score: 0

Accepted

time: 63ms

memory: 19936kb

input:

100000 100000 20
42939 95341
95341 80137
74305 80137
74305 62030
84320 62030
84320 36495
56723 36495
56723 10023
94707 10023
94707 24180
24180 79603
66069 79603
66069 47082
78855 47082
78855 1708
82047 1708
72746 82047
8294 72746
8294 63927
63927 47149
47149 8544
35907 8544
35907 90099
21705 90099
2...

output:

result:

ok 20 numbers

Test #91:

score: 0

Accepted

time: 60ms

memory: 18444kb

input:

100000 100000 50
91063 56666
56666 84770
33256 84770
92203 33256
92203 26547
50455 26547
50455 12214
12214 20646
61777 20646
61777 25527
44271 25527
44271 31371
31371 40062
52303 40062
52303 34909
34909 88370
88370 25548
86001 25548
86001 27929
27929 13692
13692 2234
24128 2234
24128 11987
54953 119...

output:

result:

ok 50 numbers

Test #92:

score: 0

Accepted

time: 60ms

memory: 18432kb

input:

100000 100000 100
79835 65625
79835 46101
46101 35569
52654 35569
18865 52654
23449 18865
23449 70124
86965 70124
5155 86965
64712 5155
15402 64712
15402 36922
55872 36922
55872 68526
88352 68526
6022 79835
6022 29039
23909 29039
23909 32123
65487 32123
88233 65487
88233 50674
74916 50674
74916 1363...

output:

result:

ok 100 numbers

Test #93:

score: 0

Accepted

time: 59ms

memory: 18536kb

input:

100000 100000 200
70876 43754
70876 97121
96062 97121
96062 37487
90682 37487
41579 90682
48324 41579
21247 48324
92500 21247
21515 92500
19971 21515
82600 19971
2954 82600
60677 2954
60677 32698
32698 13984
58449 13984
58449 87913
87913 38704
15021 38704
15021 51322
51322 56139
75697 56139
75697 47...

output:

result:

ok 200 numbers

Test #94:

score: 0

Accepted

time: 64ms

memory: 18576kb

input:

100000 100000 500
57360 64763
64763 75381
18461 75381
18461 17287
38722 17287
38722 29937
29937 31954
31954 78127
78127 17425
95713 17425
82315 95713
82315 49051
83397 49051
83397 23902
37020 23902
37020 93584
93584 29528
29528 84863
84863 93022
93022 96825
96825 25162
25162 85333
5118 85333
90315 5...

output:

result:

ok 500 numbers

Test #95:

score: 0

Accepted

time: 72ms

memory: 18400kb

input:

100000 100000 1000
99530 945
945 72420
82768 72420
82768 871
24906 871
64900 24906
64900 32592
32592 54200
54200 10811
35490 10811
35490 51493
4208 51493
15730 4208
75969 15730
75969 91410
91410 3670
59481 3670
32947 59481
32947 31713
31713 33014
33014 43209
89362 43209
41577 89362
75434 41577
75434...

output:

result:

ok 1000 numbers

Test #96:

score: 0

Accepted

time: 75ms

memory: 18652kb

input:

100000 100000 2000
46795 88145
34353 88145
34353 28718
28718 72605
99247 72605
99247 19291
6696 19291
3855 6696
3855 40768
40768 11480
11480 35942
91717 35942
91717 56952
56952 88713
88713 57883
5092 57883
29831 5092
29831 52946
91272 52946
91272 11901
91202 11901
91202 78475
29162 78475
29162 76471...

output:

result:

ok 2000 numbers

Test #97:

score: 0

Accepted

time: 77ms

memory: 19812kb

input:

100000 100000 5000
77273 56100
56100 91660
50227 91660
50227 15926
15926 92373
42060 92373
42060 74980
74980 32644
43156 32644
43156 13121
13121 72421
85187 72421
85187 59467
17511 59467
17511 13574
92386 13574
20667 92386
12338 20667
66556 12338
27196 66556
27196 58247
58247 87471
87471 46775
59404...

output:

result:

ok 5000 numbers

Test #98:

score: 0

Accepted

time: 73ms

memory: 20148kb

input:

100000 100000 10000
99625 10262
33273 10262
33273 87688
87688 28262
28262 21378
44930 21378
44930 73035
74047 73035
60258 74047
36678 60258
15988 36678
15988 96940
48407 96940
90871 48407
15765 90871
41212 15765
41212 13281
46311 13281
46311 30281
30281 91223
91223 57416
57416 30624
65673 30624
7656...

output:

result:

ok 10000 numbers

Test #99:

score: 0

Accepted

time: 71ms

memory: 20220kb

input:

100000 100000 20000
46502 14399
27374 14399
11920 27374
37881 11920
37881 83015
2129 83015
2129 85014
85014 74249
74249 85926
71766 85926
69125 71766
34215 69125
34215 13662
13662 51316
47210 51316
35931 47210
64658 35931
15298 64658
23374 15298
23374 26063
26063 96279
96279 67981
45324 67981
45324 ...

output:

result:

ok 20000 numbers

Test #100:

score: 0

Accepted

time: 66ms

memory: 19124kb

input:

100000 100000 50000
45769 24178
24178 20604
15039 20604
2050 15039
88588 2050
88588 41436
7833 41436
88477 7833
88477 6437
6437 90266
90266 98586
58347 98586
58347 25467
66701 25467
66701 79702
62348 79702
18322 62348
57153 18322
57153 60621
90360 60621
90360 99224
97984 99224
97984 30507
69662 3050...

output:

result:

ok 50000 numbers

Test #101:

score: 0

Accepted

time: 83ms

memory: 19824kb

input:

100000 100000 100000
33223 71503
48111 33223
48111 54357
54357 85597
48710 85597
87401 48710
87401 99833
52408 99833
52408 9973
21639 9973
10032 21639
53594 10032
53594 89729
56572 89729
87704 56572
93536 87704
93536 88191
34283 88191
34283 25104
43699 25104
43699 8756
8756 5017
5017 31474
31474 217...

output:

result:

ok 100000 numbers

Subtask #5:

score: 0

Time Limit Exceeded

Test #102:

score: 24

Accepted

time: 2847ms

memory: 20292kb

input:

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

output:

result:

ok 95687 numbers

Test #103:

score: 0

Accepted

time: 2804ms

memory: 20228kb

input:

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

output:

result:

ok 89370 numbers

Test #104:

score: 0

Accepted

time: 3892ms

memory: 22200kb

input:

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

output:

result:

ok 96158 numbers

Test #105:

score: -24

Time Limit Exceeded

input:

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

output:

result:

Subtask #6:

score: 0

Skipped

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted