QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#35343#961. Smol Vertex CoverFroggyguaAC ✓952ms6596kbC++172.4kb2022-06-15 11:42:502022-06-15 11:42:52

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-15 11:42:52]
  • 评测
  • 测评结果：AC
  • 用时：952ms
  • 内存：6596kb
查看
  • [2022-06-15 11:42:50]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define N 505
typedef long long ll;
mt19937 rnd(233);
int n,m,Ans,mat[N];
vector<int> G[N];
bitset<N> bk;
bool dfs(int u){
	shuffle(G[u].begin(),G[u].end(),rnd);
	bk[u]=1;
	for(auto v:G[u]){
		if(bk[mat[v]])continue;
		int t=mat[v];
		mat[u]=v,mat[v]=u,mat[t]=0;
		if(!t||dfs(t))return true;
		mat[u]=0,mat[v]=t,mat[t]=v;
	}
	return false;
}
int get_match(){
	int tot=0;
	for(int T=1;T<=3;++T){
		for(int i=1;i<=n;++i){
			if(!mat[i]){
				bk.reset();
				tot+=dfs(i);
			}
		}
	}
	return tot;
}
vector<int> H[N];
int id[N],p[N];
int dfn[N],low[N],num,tot,col[N];
bool vis[N];
inline int yes(int x){return 2*x+1;}
inline int no(int x){return 2*x;}
inline void adde(int u,int v){
	H[u].push_back(v);
	H[v^1].push_back(u^1);
}
void Clear(int n){
	for(int i=1;i<=n;++i){
		dfn[i]=low[i]=vis[i]=col[i]=0;
	}
	num=tot=0;
}
void Tarjan(int u){
	static int st[N],top;
	dfn[u]=low[u]=++num;
	vis[u]=1;
	st[++top]=u;
	for(auto v:H[u]){
		if(!dfn[v]){
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(vis[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(dfn[u]==low[u]){
		int t=0;
		++tot;
		while(t^u){
			t=st[top--];
			vis[t]=0;
			col[t]=tot;
		}
	}
}
bool check(){
	Clear(n+1);
	for(int i=2;i<=n+1;++i){
		if(!dfn[i])Tarjan(i);
	}
	for(int i=1;i<=Ans;++i){
		if(col[yes(i)]==col[no(i)]){
			return false;
		}
	}
	return true;
}
void Do(int z){
	for(int i=1;i<=n;++i){
		H[i].clear();
	}
	if(id[z]){
		adde(id[z],id[z]^1);
	}
	for(int u=1;u<=n;++u){
		if(u==z)continue;
		for(auto v:G[u]){
			if(v==z||v<u)continue;
			if(!id[u]&&!id[v]){
				return;
			}
			if(!id[u]){
				adde(id[v]^1,id[v]);
			}
			else if(!id[v]){
				adde(id[u]^1,id[u]);
			}
			else{
				if((id[u]^1)==id[v])continue;
				adde(id[u]^1,id[v]);
			}
		}
	}
	if(check()){
		cout<<Ans+(z>0)<<'\n';
		if(z)cout<<z<<' ';
		for(int i=1;i<=Ans;++i){
			cout<<(col[yes(i)]<col[no(i)]?p[yes(i)]:p[no(i)])<<' ';
		}
		exit(0);
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	Ans=get_match();
	for(int i=1,e=2;i<=n;++i){
		if(!mat[i]||id[i])continue;
		p[id[i]=e++]=i;
		p[id[mat[i]]=e++]=mat[i];
	}
	Do(0);
	for(int i=1;i<=n;++i){
		Do(i);
	}
	cout<<"not smol\n";
	return 0;
}
源文件, 语言: C++17

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3492kb

input:

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

output:

3
1 5 3

result:

ok vertex cover of size 3

Test #2:

score: 0
Accepted
time: 2ms
memory: 3620kb

input:

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

output:

not smol

result:

ok not smol

Test #3:

score: 0
Accepted
time: 2ms
memory: 3644kb

input:

3 0

output:

0

result:

ok vertex cover of size 0

Test #4:

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

input:

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

output:

5
1 2 3 6 7

result:

ok vertex cover of size 5

Test #5:

score: 0
Accepted
time: 2ms
memory: 3624kb

input:

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

output:

6
2 1 6 7 10 8

result:

ok vertex cover of size 6

Test #6:

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

input:

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

output:

not smol

result:

ok not smol

Test #7:

score: 0
Accepted
time: 2ms
memory: 3512kb

input:

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

output:

not smol

result:

ok not smol

Test #8:

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

input:

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

output:

not smol

result:

ok not smol

Test #9:

score: 0
Accepted
time: 3ms
memory: 3656kb

input:

200 300
64 134
92 154
82 142
33 198
26 185
24 74
32 144
26 118
113 122
98 130
74 84
70 184
45 181
44 136
44 134
67 185
77 160
21 50
80 181
62 78
196 199
37 174
91 105
17 74
158 166
26 172
70 129
128 133
152 173
15 86
37 67
55 91
45 74
60 141
179 184
22 168
65 161
62 67
117 152
174 181
35 99
80 103
3...

output:

not smol

result:

ok not smol

Test #10:

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

input:

200 1000
19 159
64 180
15 88
82 136
22 57
92 200
86 87
176 194
57 106
116 179
101 128
27 137
41 71
35 139
48 153
177 178
80 131
9 156
29 122
101 148
88 163
90 116
16 72
8 166
100 116
97 161
19 143
78 163
23 119
104 146
91 161
52 66
183 196
29 123
84 86
41 109
65 76
82 161
138 182
108 156
35 94
101 1...

output:

not smol

result:

ok not smol

Test #11:

score: 0
Accepted
time: 15ms
memory: 3952kb

input:

200 5000
60 81
22 145
156 181
27 44
49 89
69 176
61 64
16 199
46 50
75 103
26 168
6 35
60 75
51 117
41 105
20 154
69 100
75 195
22 115
67 72
170 190
31 115
10 200
51 129
14 147
161 163
9 72
22 113
70 87
112 184
28 81
178 197
72 180
171 192
71 116
71 174
30 95
20 157
50 125
142 184
18 130
82 110
65 1...

output:

not smol

result:

ok not smol

Test #12:

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

input:

500 300
201 309
17 37
39 176
416 493
86 475
163 215
127 283
122 274
107 412
7 93
294 434
335 360
50 87
364 372
55 192
341 411
236 299
286 349
79 208
137 470
141 421
21 324
4 165
232 473
367 397
400 475
30 77
177 435
116 133
115 281
416 482
198 498
300 410
173 457
176 450
157 179
402 425
219 486
39 3...

output:

147
3 4 5 6 7 94 176 12 354 399 17 18 20 21 22 410 24 202 181 30 32 34 39 109 43 44 242 46 86 49 50 285 52 54 55 394 481 313 60 64 459 67 68 483 188 73 76 78 208 294 82 85 91 92 95 96 99 101 201 107 395 110 113 183 471 116 118 120 121 122 443 127 231 345 159 470 140 421 403 146 370 151 152 179 158 1...

result:

ok vertex cover of size 147

Test #13:

score: 0
Accepted
time: 8ms
memory: 3724kb

input:

500 1000
232 237
263 478
147 353
131 318
45 109
218 452
377 436
61 326
29 372
394 484
72 374
312 449
451 461
26 113
25 188
21 282
453 484
261 295
449 489
225 422
125 168
123 449
23 211
251 484
40 185
38 304
6 337
71 142
287 356
315 413
185 411
68 111
453 457
70 187
20 183
107 361
324 466
277 483
10 ...

output:

not smol

result:

ok not smol

Test #14:

score: 0
Accepted
time: 48ms
memory: 4064kb

input:

500 5000
78 84
13 468
95 135
258 447
258 267
226 321
132 282
238 355
194 248
75 485
325 390
46 182
156 284
272 289
204 361
15 228
322 448
410 430
35 317
227 386
325 398
207 443
36 280
73 153
117 459
396 494
234 430
140 199
49 357
26 128
177 210
15 231
351 379
357 484
299 489
376 454
177 377
228 331
...

output:

not smol

result:

ok not smol

Test #15:

score: 0
Accepted
time: 952ms
memory: 6596kb

input:

500 124750
260 435
24 351
41 342
79 458
63 342
463 485
313 372
88 486
300 435
144 440
88 480
83 373
126 356
129 486
118 416
83 138
439 447
59 222
1 162
367 487
137 286
253 261
255 451
329 461
276 328
66 184
76 441
228 492
93 396
288 420
2 424
257 318
216 342
249 474
152 200
206 485
13 332
353 406
20...

output:

not smol

result:

ok not smol

Test #16:

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

input:

20 20
12 17
15 18
14 20
3 19
11 12
5 14
6 20
2 6
13 19
6 18
3 20
13 18
8 19
1 9
4 12
1 5
10 14
10 13
10 12
7 11

output:

9
1 2 20 12 5 11 19 10 18

result:

ok vertex cover of size 9

Test #17:

score: 0
Accepted
time: 3ms
memory: 3596kb

input:

20 40
5 12
10 17
9 15
4 7
8 17
11 12
6 16
8 11
1 15
14 18
9 17
1 6
8 14
3 5
10 15
4 18
3 20
9 14
7 19
2 12
9 19
6 18
10 20
4 13
3 14
4 8
17 18
3 15
18 20
1 17
5 9
7 14
4 9
7 20
6 7
2 7
8 15
13 15
4 16
2 18

output:

10
1 18 3 13 16 7 8 9 10 12

result:

ok vertex cover of size 10

Test #18:

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

input:

20 70
3 4
4 8
7 17
2 7
5 7
3 15
1 16
5 10
13 20
10 19
7 15
8 9
6 16
11 20
18 19
3 5
6 17
1 5
9 11
4 12
15 18
1 15
18 20
5 18
8 14
1 14
10 20
8 17
7 9
13 14
6 14
11 19
4 7
5 8
13 19
4 6
6 9
2 18
10 14
2 10
6 20
12 14
10 15
2 8
1 19
14 18
11 17
3 9
16 18
1 17
11 16
6 19
7 19
13 16
8 19
7 14
12 15
1 2
...

output:

10
1 10 3 11 8 6 7 12 13 18

result:

ok vertex cover of size 10

Test #19:

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

input:

110 50
48 64
54 66
9 76
53 54
54 99
50 100
98 100
48 83
48 63
16 103
87 110
14 110
45 57
71 103
99 103
11 54
38 110
57 102
29 110
2 107
44 110
94 100
9 46
24 32
47 88
36 57
24 34
63 100
12 48
59 103
9 15
2 103
21 57
54 62
12 103
47 108
11 107
54 106
47 75
9 64
24 95
38 100
78 107
48 60
2 9
9 59
39 4...

output:

10
110 107 9 54 48 103 57 24 100 47

result:

ok vertex cover of size 10

Test #20:

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

input:

110 300
43 59
21 78
41 53
8 37
51 55
10 58
36 81
51 105
8 104
69 101
15 84
8 29
4 69
8 83
53 54
51 54
64 69
61 69
50 53
15 46
43 47
51 108
29 69
57 81
16 18
51 109
8 99
18 37
1 43
10 96
15 95
10 14
15 107
8 50
36 51
51 78
81 94
10 66
12 51
69 102
43 63
27 81
8 72
15 44
14 53
43 54
28 69
43 68
69 108...

output:

10
15 8 81 18 21 10 69 43 53 51

result:

ok vertex cover of size 10

Test #21:

score: 0
Accepted
time: 2ms
memory: 3724kb

input:

110 700
42 93
34 45
52 109
26 102
34 100
34 43
57 87
33 34
25 88
42 50
34 62
36 95
60 106
21 87
81 87
99 106
42 56
1 8
78 87
25 48
42 43
8 68
8 104
14 42
13 34
35 109
99 109
39 42
35 102
26 106
42 57
22 42
97 102
1 95
95 100
45 102
31 102
22 34
59 87
82 96
20 106
25 69
8 77
13 25
25 63
49 96
34 57
8...

output:

10
106 87 42 25 95 34 102 8 96 109

result:

ok vertex cover of size 10

Test #22:

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

input:

200 500
9 78
21 41
6 189
106 172
73 198
124 154
71 111
24 77
3 22
193 194
143 187
147 192
11 127
35 49
5 60
139 161
52 96
14 51
28 163
57 105
12 154
155 159
153 187
130 133
71 132
15 95
5 29
119 153
78 96
117 159
69 170
180 188
147 151
28 62
3 142
52 77
1 192
62 68
75 135
8 191
145 187
114 157
91 14...

output:

100
1 93 3 4 5 62 7 191 121 10 150 12 46 63 15 91 118 81 164 20 193 72 61 24 25 26 41 135 42 137 126 32 142 49 184 109 37 38 39 167 43 44 45 47 144 125 51 52 158 55 105 127 64 65 174 67 170 128 73 117 147 112 78 189 123 185 84 171 86 87 88 89 90 145 139 197 100 104 106 173 111 116 119 188 122 124 12...

result:

ok vertex cover of size 100

Test #23:

score: 0
Accepted
time: 3ms
memory: 3732kb

input:

200 3000
109 154
86 90
5 157
30 132
114 162
133 160
88 151
40 112
33 36
76 142
69 171
81 118
115 144
65 128
33 192
178 182
44 91
51 98
94 111
29 122
62 109
8 72
122 195
165 175
74 104
116 126
94 114
139 170
6 192
168 169
67 190
59 64
110 186
62 148
49 180
33 141
81 88
102 165
1 120
116 180
33 111
34...

output:

100
1 118 3 4 116 57 35 8 30 36 11 12 78 105 86 16 29 48 19 153 27 152 23 24 25 26 28 31 147 133 179 159 169 45 191 43 190 46 115 49 58 51 89 53 114 55 164 61 60 62 64 70 71 184 73 75 91 189 80 87 82 83 157 85 88 161 119 135 142 112 154 138 101 128 103 104 199 187 108 178 185 111 113 176 196 172 143...

result:

ok vertex cover of size 100

Test #24:

score: 0
Accepted
time: 4ms
memory: 3900kb

input:

200 8000
149 157
84 176
17 73
100 132
25 181
171 200
16 35
5 78
97 126
113 171
24 184
117 143
40 108
96 192
9 139
109 179
101 161
114 127
156 167
14 161
128 156
71 190
51 183
51 140
74 104
119 151
65 71
158 174
138 161
160 192
9 158
27 67
55 162
100 102
159 174
63 81
47 195
40 148
36 121
107 181
33 ...

output:

100
1 2 105 108 5 65 7 58 182 10 11 59 54 163 169 16 137 19 20 21 69 111 24 37 28 29 30 31 32 104 177 89 36 38 46 115 41 42 98 161 140 123 135 130 52 158 183 57 60 61 62 124 128 162 67 196 72 73 195 75 116 120 81 79 80 119 83 190 85 86 139 129 91 112 194 189 110 159 100 171 109 185 117 118 192 126 1...

result:

ok vertex cover of size 100

Test #25:

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

input:

500 500
271 342
280 463
424 444
322 342
200 239
239 358
449 469
239 269
54 63
98 342
375 488
245 449
338 342
18 63
188 359
274 280
3 449
239 241
75 239
42 239
280 425
375 486
8 280
95 388
321 342
39 280
95 487
219 449
188 312
188 417
270 424
92 375
264 280
59 280
188 444
79 399
188 418
320 424
156 3...

output:

10
399 424 63 280 375 239 188 449 95 342

result:

ok vertex cover of size 10

Test #26:

score: 0
Accepted
time: 3ms
memory: 3660kb

input:

500 1000
9 316
133 491
9 89
55 82
247 480
133 364
139 317
168 411
60 168
339 365
247 279
72 488
55 160
5 339
247 343
60 81
247 483
55 76
139 494
168 374
168 215
21 339
81 500
81 374
143 391
55 207
37 55
168 253
205 391
9 92
2 168
9 70
55 441
9 278
168 335
437 488
9 396
391 411
55 318
81 161
2 247
27...

output:

10
488 168 247 391 339 81 133 139 9 55

result:

ok vertex cover of size 10

Test #27:

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

input:

500 4000
34 440
276 370
287 292
23 449
23 400
34 179
44 317
23 115
30 34
276 388
88 129
276 415
165 300
123 249
300 445
122 287
276 431
283 484
30 283
23 169
276 460
170 270
164 283
123 397
23 263
129 175
208 287
300 315
170 292
66 170
287 375
126 276
287 441
287 487
88 287
300 418
262 276
44 206
11...

output:

10
276 23 287 129 170 44 283 123 34 300

result:

ok vertex cover of size 10

Test #28:

score: 0
Accepted
time: 3ms
memory: 3728kb

input:

500 500
12 25
334 479
235 352
343 496
120 445
178 477
93 477
124 364
55 294
222 463
29 191
18 107
38 97
142 451
29 78
237 438
98 196
26 234
16 189
15 311
297 339
107 300
176 442
218 222
8 396
335 336
456 474
276 495
130 350
59 498
18 441
303 376
308 357
10 35
114 470
403 476
234 282
132 372
6 37
179...

output:

188
1 2 3 4 37 8 9 116 11 66 13 47 15 16 17 239 19 20 22 23 70 25 26 27 28 29 30 288 32 178 34 35 36 38 293 41 42 43 44 45 46 348 332 52 424 487 294 56 57 59 390 328 291 377 217 65 196 71 420 213 419 75 237 137 79 234 81 408 113 86 483 257 92 93 94 436 381 97 100 157 324 103 421 105 107 379 109 154 ...

result:

ok vertex cover of size 188

Test #29:

score: 0
Accepted
time: 10ms
memory: 3804kb

input:

500 3000
27 174
78 179
309 321
33 313
219 225
203 316
30 149
266 270
106 350
369 463
74 433
54 398
82 296
276 430
291 419
122 412
343 427
76 163
113 398
147 482
113 263
56 411
383 396
115 149
161 276
130 207
163 297
191 283
2 68
25 419
120 414
133 409
308 321
235 476
89 176
46 130
80 113
293 405
52 ...

output:

200
1 25 339 4 482 442 283 387 275 46 414 12 490 14 176 16 199 216 19 20 224 23 280 437 27 28 428 30 80 32 183 293 36 37 462 197 322 42 396 143 203 48 274 50 51 123 53 196 263 56 57 58 380 447 358 62 63 253 444 106 68 71 72 73 193 495 76 77 78 215 296 245 181 319 139 87 449 430 90 124 92 307 172 200...

result:

ok vertex cover of size 200

Test #30:

score: 0
Accepted
time: 14ms
memory: 3936kb

input:

500 8000
94 339
209 235
86 449
123 181
230 282
69 341
199 324
21 194
7 72
36 379
75 234
73 84
233 379
148 377
32 56
5 264
111 453
246 475
32 96
202 433
235 328
49 298
104 346
349 427
243 484
104 380
10 477
303 318
57 90
84 347
65 442
188 212
318 323
283 404
127 463
26 490
58 160
430 456
21 147
5 35
...

output:

200
1 206 3 4 5 6 7 286 9 10 11 12 13 14 15 436 355 168 19 123 21 492 23 24 280 26 27 28 239 30 31 32 327 34 377 212 224 298 39 200 150 316 43 442 308 331 460 48 388 51 409 217 54 63 283 102 59 60 136 486 453 68 69 115 270 250 113 76 89 78 79 273 202 333 83 84 85 86 129 90 91 92 93 94 95 121 383 249...

result:

ok vertex cover of size 200

Test #31:

score: 0
Accepted
time: 40ms
memory: 4176kb

input:

500 20000
280 430
283 415
147 154
343 433
59 417
47 474
14 204
56 80
193 416
296 484
112 140
193 291
147 238
98 255
106 358
39 424
8 295
309 370
96 132
68 432
237 454
69 119
98 218
308 343
12 372
105 272
147 421
108 110
121 161
16 44
225 286
17 328
327 329
72 170
52 260
295 302
170 347
20 281
37 66
...

output:

200
1 104 441 4 19 350 485 453 303 10 80 12 27 352 15 203 181 449 428 386 447 23 407 215 86 459 46 221 31 385 484 34 339 36 403 432 39 219 319 42 356 44 67 47 48 259 197 51 52 336 250 397 354 58 433 109 338 62 281 314 65 66 488 92 85 71 72 408 285 347 299 78 190 253 83 237 87 470 89 90 420 410 94 30...

result:

ok vertex cover of size 200

Test #32:

score: 0
Accepted
time: 85ms
memory: 4928kb

input:

500 50000
103 130
189 432
290 497
46 337
113 237
249 333
162 376
181 272
30 101
58 192
252 362
374 424
85 322
201 432
163 340
74 99
69 424
189 416
160 343
235 425
70 304
50 322
21 370
38 338
395 469
141 468
146 471
282 497
249 265
131 292
6 417
239 326
243 347
155 167
130 209
17 302
189 222
100 291
...

output:

200
151 31 375 4 5 312 369 348 80 10 94 138 13 14 162 16 17 18 19 20 67 22 208 394 145 26 388 88 30 32 33 466 398 36 37 306 322 40 336 42 120 44 45 46 404 96 49 269 261 107 180 54 182 406 248 270 60 167 62 63 460 65 239 72 70 71 382 93 219 76 424 492 81 82 83 132 178 440 89 372 92 228 397 99 100 314...

result:

ok vertex cover of size 200

Test #33:

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

input:

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

output:

3
4 2 9

result:

ok vertex cover of size 3

Test #34:

score: 0
Accepted
time: 2ms
memory: 3624kb

input:

10 15
6 10
7 10
6 7
3 7
2 3
8 10
2 8
4 10
4 7
1 7
2 9
7 8
2 7
2 6
2 10

output:

3
7 2 10

result:

ok vertex cover of size 3

Test #35:

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

input:

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

output:

6
2 1 4 7 10 8

result:

ok vertex cover of size 6

Test #36:

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

input:

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

output:

6
7 9 10 3 5 6

result:

ok vertex cover of size 6

Test #37:

score: 0
Accepted
time: 2ms
memory: 3768kb

input:

100 70
8 82
29 50
29 54
65 97
42 43
4 65
42 84
8 16
17 42
62 65
40 82
12 65
65 99
29 86
29 41
56 65
8 58
32 42
63 85
42 64
65 71
45 65
63 95
22 29
63 87
16 29
24 29
34 42
42 50
46 82
78 82
10 42
52 82
29 94
42 89
42 82
39 82
29 45
42 91
39 63
42 70
29 81
8 51
61 65
8 47
72 82
65 98
31 63
82 98
42 60...

output:

6
65 8 42 29 63 82

result:

ok vertex cover of size 6

Test #38:

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

input:

100 222
77 94
75 77
40 87
36 53
21 46
46 56
46 75
31 74
43 77
41 77
67 77
77 81
4 100
55 86
47 77
65 71
58 75
49 94
27 78
32 36
46 94
4 77
42 77
7 71
40 72
1 27
37 93
22 40
50 77
46 74
77 92
86 93
27 59
77 80
36 70
53 100
4 73
77 98
32 55
53 93
34 100
66 93
62 93
72 77
73 77
69 71
40 88
36 57
52 94
...

output:

13
46 40 4 31 55 36 71 58 93 94 77 27 100

result:

ok vertex cover of size 13

Test #39:

score: 0
Accepted
time: 3ms
memory: 3752kb

input:

100 1000
22 84
10 46
40 91
10 49
29 89
6 18
5 7
49 76
73 83
42 56
67 82
26 31
49 50
55 100
26 52
68 80
26 61
40 43
39 46
72 99
4 91
6 67
4 61
25 99
54 65
58 99
46 68
51 93
54 94
33 85
16 84
45 75
76 84
25 61
50 84
31 71
26 69
61 100
86 100
10 51
31 82
50 66
47 69
24 69
66 99
7 75
21 31
39 51
69 79
3...

output:

30
68 13 89 18 52 6 7 83 84 10 92 100 85 57 45 94 46 78 51 65 69 99 82 31 91 61 50 56 40 76

result:

ok vertex cover of size 30

Test #40:

score: 0
Accepted
time: 3ms
memory: 3676kb

input:

100 1500
7 71
5 24
13 88
69 89
62 78
1 19
90 96
6 76
54 78
17 20
30 51
52 88
39 97
36 44
24 89
28 97
14 48
29 53
25 67
5 89
28 46
7 89
60 67
16 25
3 69
1 84
16 99
15 88
6 79
28 100
27 60
7 53
60 61
54 61
24 30
22 41
78 92
70 94
42 86
27 34
45 100
25 34
59 67
37 53
34 68
25 48
76 77
65 78
24 80
17 54...

output:

38
1 17 3 55 5 59 70 63 39 25 30 64 14 15 16 18 76 79 41 78 86 53 28 75 54 88 74 34 90 80 57 44 45 87 71 60 89 92

result:

ok vertex cover of size 38

Test #41:

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

input:

100 200
30 77
23 42
4 5
47 67
5 67
4 67
42 98
15 65
40 62
74 77
4 34
42 88
40 100
40 50
49 63
56 77
40 81
59 63
33 90
65 80
31 40
4 95
4 24
17 90
9 54
40 75
1 77
63 84
51 65
40 89
31 65
40 98
65 74
16 67
61 67
67 83
54 89
40 71
54 59
29 63
47 63
4 62
13 67
4 17
63 85
42 62
57 90
78 90
85 90
4 69
14 ...

output:

9
77 4 90 42 63 65 54 67 40

result:

ok vertex cover of size 9

Test #42:

score: 0
Accepted
time: 3ms
memory: 3572kb

input:

100 542
13 26
6 84
55 96
54 89
22 76
21 33
54 83
39 47
14 95
54 100
21 99
34 35
9 47
32 99
12 42
72 89
72 97
55 73
13 22
39 86
21 50
63 89
48 56
83 89
72 84
69 72
53 77
29 82
31 63
13 48
38 84
54 91
4 13
12 67
69 82
34 54
29 76
53 93
70 98
54 94
41 84
7 39
31 83
56 61
12 96
10 39
3 94
53 79
72 88
83...

output:

26
55 86 14 54 31 89 92 39 9 22 99 12 13 34 70 64 72 21 84 82 94 29 77 56 46 53

result:

ok vertex cover of size 26

Test #43:

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

input:

100 1320
55 58
21 34
3 51
14 38
1 70
8 89
79 97
19 57
60 86
35 64
10 50
73 76
12 66
18 32
95 100
65 71
12 44
26 100
15 50
26 38
1 58
12 41
75 86
23 42
2 44
35 90
70 88
15 66
18 59
28 87
32 78
17 54
43 53
56 66
40 96
5 75
34 97
6 59
62 66
9 85
2 38
23 75
12 80
86 95
4 42
3 66
17 71
68 73
50 89
30 84
...

output:

50
1 2 3 4 18 6 40 8 87 11 12 32 45 53 57 23 46 21 22 75 25 26 56 73 67 30 31 34 35 71 38 94 41 59 44 79 50 66 54 55 85 61 93 100 80 72 69 88 86 97

result:

ok vertex cover of size 50

Test #44:

score: 0
Accepted
time: 3ms
memory: 3804kb

input:

100 2530
81 86
11 29
75 96
10 24
57 92
47 73
67 96
4 61
23 99
3 84
1 18
78 96
20 23
4 97
1 73
45 74
12 43
33 100
8 43
1 86
40 77
33 58
21 95
7 28
23 46
77 88
25 33
14 60
8 85
24 48
37 90
54 60
59 78
51 85
14 73
48 79
8 41
19 87
58 81
56 60
56 81
26 44
21 32
33 85
64 85
42 85
64 96
41 91
8 96
43 94
4...

output:

44
1 24 3 4 76 60 7 8 41 10 11 55 43 68 15 23 61 18 20 96 39 73 92 28 62 30 31 32 33 81 95 37 78 44 45 79 47 51 52 85 90 77 80 87

result:

ok vertex cover of size 44

Test #45:

score: 0
Accepted
time: 2ms
memory: 3752kb

input:

500 700
163 469
134 331
95 134
72 185
46 185
131 163
163 263
185 398
185 343
188 265
134 260
134 176
76 185
134 273
163 389
185 218
265 398
185 323
134 315
112 163
185 393
163 441
185 273
134 174
163 323
108 265
163 299
134 333
92 134
198 265
75 265
265 277
163 492
134 436
265 413
134 181
185 309
9 ...

output:

4
185 265 134 163

result:

ok vertex cover of size 4

Test #46:

score: 0
Accepted
time: 2ms
memory: 3764kb

input:

500 2222
83 129
167 330
115 388
206 469
39 398
220 325
214 232
119 315
68 348
168 246
348 370
209 395
173 251
12 266
88 206
206 246
14 218
233 392
101 300
209 453
195 233
129 391
88 168
23 346
119 300
57 230
298 388
99 300
97 230
138 408
183 329
243 447
250 315
330 397
216 266
15 168
149 233
120 233...

output:

23
14 230 206 346 173 6 447 408 300 329 429 315 214 168 325 129 388 209 348 233 39 330 266

result:

ok vertex cover of size 23

Test #47:

score: 0
Accepted
time: 23ms
memory: 3892kb

input:

500 10000
188 494
326 448
330 493
239 259
89 130
173 383
250 445
181 380
176 395
112 320
52 228
30 317
383 392
52 212
238 363
92 490
192 208
91 188
88 363
97 419
131 141
186 500
289 411
3 50
240 443
26 112
70 238
55 178
56 94
37 231
119 174
52 402
210 258
131 349
65 493
11 390
12 418
43 397
11 498
2...

output:

100
474 319 3 348 5 488 352 43 248 10 11 12 262 14 229 258 497 56 389 310 186 334 182 58 85 434 274 374 445 119 435 192 323 419 406 493 193 383 188 41 45 370 259 156 464 317 261 428 52 269 273 55 130 59 330 297 326 228 359 140 357 181 407 305 351 175 292 220 238 275 131 283 91 133 311 411 88 335 231...

result:

ok vertex cover of size 100

Test #48:

score: 0
Accepted
time: 62ms
memory: 5424kb

input:

500 89505
63 230
260 427
211 269
185 348
394 402
142 308
48 186
123 257
7 496
74 227
97 274
156 175
212 279
174 329
10 293
56 221
11 187
48 70
19 203
128 305
22 179
183 402
457 493
89 233
174 472
1 457
258 338
180 305
5 79
125 227
79 499
350 353
140 162
81 451
64 387
284 376
24 182
299 327
66 396
71...

output:

234
134 2 3 4 5 6 7 8 9 114 11 466 13 110 143 64 368 283 19 279 21 337 23 154 488 26 126 385 30 403 472 376 34 112 413 57 38 39 40 86 42 340 88 45 267 47 48 326 50 51 214 217 179 55 56 286 106 499 347 442 457 66 67 182 71 428 72 445 145 287 348 77 194 79 80 209 82 301 210 168 87 89 90 280 163 309 95...

result:

ok vertex cover of size 234

Test #49:

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

input:

500 900
7 417
97 388
305 372
102 220
62 351
161 264
191 239
84 244
391 460
245 358
89 303
129 138
64 355
121 200
197 325
35 436
131 375
74 148
171 305
191 388
84 151
329 492
16 444
16 347
24 324
92 376
248 388
231 398
189 409
320 392
301 485
422 490
275 500
36 454
41 221
252 490
162 215
35 445
214 3...

output:

181
1 2 342 4 357 6 7 8 9 10 167 12 207 190 222 16 472 240 474 187 21 41 62 95 312 346 209 265 30 436 414 255 35 36 348 478 39 40 263 471 335 227 291 467 352 129 89 247 146 54 55 56 325 58 282 60 61 277 64 364 66 154 68 69 395 200 202 148 75 292 371 78 308 324 217 311 287 84 85 168 165 449 117 206 9...

result:

ok vertex cover of size 181

Test #50:

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

input:

500 3222
459 494
86 232
124 377
147 320
195 230
479 496
58 364
290 324
195 389
19 424
5 324
134 309
88 489
99 489
195 497
98 109
387 489
140 239
119 150
70 424
309 355
34 195
489 497
29 425
98 463
455 496
310 489
98 316
214 309
437 496
359 494
119 253
361 377
13 364
22 51
377 404
424 455
310 494
316...

output:

17
195 119 147 489 22 309 239 425 86 324 496 364 250 424 377 494 98

result:

ok vertex cover of size 17

Test #51:

score: 0
Accepted
time: 22ms
memory: 3876kb

input:

500 9900
68 260
76 109
427 464
109 464
364 436
259 427
138 371
108 477
52 148
38 363
172 422
142 197
392 425
15 339
99 226
99 228
25 118
81 336
15 72
252 336
265 480
73 498
113 337
418 468
169 272
380 494
273 336
45 69
189 290
9 95
155 159
45 64
95 227
345 446
48 494
148 151
93 439
192 354
13 267
26...

output:

91
142 265 109 178 213 100 327 248 278 86 334 34 435 456 15 226 113 23 267 416 22 496 25 158 66 135 29 124 379 236 176 484 84 64 471 192 345 311 185 217 44 45 116 430 336 477 257 127 165 436 495 489 57 354 410 73 363 67 458 290 494 244 72 138 75 425 234 233 468 159 367 148 357 479 486 301 260 91 93 ...

result:

ok vertex cover of size 91

Test #52:

score: 0
Accepted
time: 83ms
memory: 5468kb

input:

500 86247
121 224
151 297
213 289
12 408
112 284
128 369
234 499
195 396
268 305
158 500
247 299
358 403
330 375
71 212
78 477
12 463
220 457
322 384
191 286
111 437
223 495
419 464
2 447
292 303
149 474
250 326
108 150
61 346
292 333
121 258
223 231
81 90
150 389
178 266
127 331
14 346
28 291
432 4...

output:

222
84 2 224 155 5 6 304 334 9 337 133 12 281 14 15 108 17 464 186 95 30 125 289 25 26 149 28 31 146 81 34 305 36 85 442 39 40 445 207 75 44 89 264 47 482 49 392 51 139 53 215 55 56 352 58 449 66 195 299 168 64 65 109 112 69 70 340 441 230 74 315 92 78 79 80 82 454 86 238 381 93 111 97 128 237 192 1...

result:

ok vertex cover of size 222

Test #53:

score: 0
Accepted
time: 2ms
memory: 3496kb

input:

7 15
3 6
1 2
5 6
2 6
2 7
1 5
3 5
1 3
2 5
3 4
3 7
2 4
4 7
5 7
1 4

output:

4
2 3 5 4

result:

ok vertex cover of size 4

Test #54:

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

input:

7 16
5 6
1 2
2 3
3 4
2 7
3 5
2 6
2 4
3 7
1 4
4 5
4 6
1 5
1 7
6 7
5 7

output:

4
7 2 5 4

result:

ok vertex cover of size 4

Test #55:

score: 0
Accepted
time: 2ms
memory: 3616kb

input:

38 70
6 18
12 34
25 31
6 20
16 23
15 26
3 34
3 15
17 18
14 23
22 33
1 7
30 36
26 38
10 32
7 38
22 23
23 25
7 30
29 33
17 27
1 20
25 38
28 36
3 21
10 20
10 11
23 27
16 18
4 19
6 14
5 18
25 34
24 29
21 38
18 22
19 30
1 22
26 27
13 32
1 6
5 36
3 14
18 32
6 9
4 36
5 17
29 34
4 26
16 20
21 35
21 32
13 15...

output:

20
1 20 8 3 4 18 6 7 30 10 12 13 33 17 21 23 29 25 26 36

result:

ok vertex cover of size 20

Test #56:

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

input:

20 22
1 3
1 8
1 15
2 7
2 14
3 6
3 13
4 5
4 12
5 11
5 20
6 10
6 19
7 9
7 18
8 17
9 16
10 15
11 14
12 13
16 20
17 19

output:

10
1 3 7 5 6 17 16 10 14 12

result:

ok vertex cover of size 10

Test #57:

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

input:

100 88
18 41
29 74
53 70
6 60
45 63
69 100
1 92
31 42
26 76
49 78
28 42
47 84
28 68
31 56
87 95
46 80
5 60
47 89
10 21
73 97
2 15
13 30
18 88
44 77
39 64
16 65
20 82
88 99
49 87
29 98
18 68
53 55
28 78
13 22
82 90
28 72
26 33
8 19
66 100
85 96
23 46
34 92
53 81
34 67
2 36
45 60
5 31
58 93
59 85
75 9...

output:

37
92 2 5 60 7 19 97 21 16 13 18 82 65 46 39 26 62 28 29 31 32 34 36 93 40 41 44 63 47 49 53 55 85 100 91 95 99

result:

ok vertex cover of size 37

Test #58:

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

input:

130 197
121 129
105 119
51 119
25 36
36 111
27 56
94 115
26 44
64 100
18 50
31 60
29 95
89 125
75 122
80 128
48 130
9 13
70 96
5 70
26 100
30 71
63 87
12 92
41 88
9 30
8 106
6 81
26 61
3 41
78 92
34 50
106 117
33 83
10 11
18 101
31 94
39 88
5 67
1 129
17 109
73 90
37 49
20 27
18 71
21 67
8 35
51 87
...

output:

63
9 1 77 41 79 5 6 112 106 30 10 129 67 14 15 16 109 101 19 114 21 22 90 24 25 26 27 29 31 42 83 50 35 36 37 58 88 43 44 71 47 93 128 87 52 57 54 116 130 97 64 102 68 96 119 107 75 92 85 125 115 98 104

result:

ok vertex cover of size 63

Test #59:

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

input:

150 218
7 41
31 149
60 93
64 137
95 127
53 121
31 129
105 127
15 93
104 113
10 11
52 103
34 100
35 71
20 39
2 4
126 136
98 134
89 132
75 124
53 111
107 136
9 83
81 106
54 77
18 107
3 115
10 138
81 126
1 53
10 116
39 43
89 105
19 110
17 70
24 126
4 121
40 46
3 138
106 124
137 149
91 123
74 139
56 134...

output:

70
1 92 2 3 76 59 6 7 8 9 10 70 14 16 107 75 146 22 128 100 44 117 62 80 129 31 32 114 81 71 38 39 122 123 51 46 110 134 50 103 53 54 55 112 57 91 94 104 137 72 73 74 93 85 86 130 132 90 95 96 143 98 119 105 124 116 125 121 126 141

result:

ok vertex cover of size 70

Test #60:

score: 0
Accepted
time: 2ms
memory: 3636kb

input:

200 771
1 3
1 8
1 15
1 24
1 35
1 48
1 63
1 80
1 99
1 120
1 143
1 168
1 195
2 7
2 14
2 23
2 34
2 47
2 62
2 79
2 98
2 119
2 142
2 167
2 194
3 6
3 13
3 22
3 33
3 46
3 61
3 78
3 97
3 118
3 141
3 166
3 193
4 5
4 12
4 21
4 32
4 45
4 60
4 77
4 96
4 117
4 140
4 165
4 192
5 11
5 20
5 31
5 44
5 59
5 76
5 95
5...

output:

not smol

result:

ok not smol

Test #61:

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

input:

200 332
107 175
70 76
127 193
108 191
183 189
140 178
80 90
21 193
115 155
10 12
69 176
101 188
30 41
23 116
70 197
40 71
71 155
13 153
145 177
38 48
54 115
96 135
118 175
110 167
157 180
5 125
106 175
77 139
52 148
168 175
110 120
4 133
91 191
101 160
59 92
41 158
91 97
36 181
44 107
146 162
3 28
5...

output:

not smol

result:

ok not smol

Test #62:

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

input:

219 885
1 3
1 8
1 15
1 24
1 35
1 48
1 63
1 80
1 99
1 120
1 143
1 168
1 195
2 7
2 14
2 23
2 34
2 47
2 62
2 79
2 98
2 119
2 142
2 167
2 194
3 6
3 13
3 22
3 33
3 46
3 61
3 78
3 97
3 118
3 141
3 166
3 193
4 5
4 12
4 21
4 32
4 45
4 60
4 77
4 96
4 117
4 140
4 165
4 192
5 11
5 20
5 31
5 44
5 59
5 76
5 95
5...

output:

not smol

result:

ok not smol

Test #63:

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

input:

222 276
106 214
40 143
2 138
194 199
139 217
4 208
137 219
41 125
49 190
78 94
63 219
65 141
44 93
123 151
117 132
150 210
148 183
124 219
4 47
133 196
46 82
144 151
77 219
27 113
139 197
52 112
69 148
68 106
32 147
145 206
166 203
93 211
70 142
103 217
30 177
38 108
160 194
69 111
158 180
26 172
14...

output:

97
82 2 112 4 5 179 7 8 9 10 11 14 88 43 16 145 18 131 20 133 27 23 24 132 26 178 29 177 31 32 33 117 35 57 38 39 40 125 206 89 77 174 137 59 52 83 55 60 172 196 142 64 141 204 190 69 70 72 122 78 138 80 81 157 215 91 93 94 95 96 166 165 103 104 106 107 114 201 115 181 121 123 189 170 199 135 139 14...

result:

ok vertex cover of size 97

Test #64:

score: 0
Accepted
time: 48ms
memory: 4092kb

input:

222 13624
111 180
5 112
145 215
139 173
38 130
38 184
7 17
113 165
128 216
133 177
29 172
64 106
24 156
156 171
62 127
45 138
139 157
59 69
57 84
119 146
164 178
130 190
123 125
12 195
42 169
13 219
69 92
130 147
23 40
78 88
101 102
128 217
69 183
69 131
196 203
47 189
126 221
49 64
49 124
40 62
54 ...

output:

not smol

result:

ok not smol

Test #65:

score: 0
Accepted
time: 2ms
memory: 3652kb

input:

222 905
1 3
1 8
1 15
1 24
1 35
1 48
1 63
1 80
1 99
1 120
1 143
1 168
1 195
2 7
2 14
2 23
2 34
2 47
2 62
2 79
2 98
2 119
2 142
2 167
2 194
3 6
3 13
3 22
3 33
3 46
3 61
3 78
3 97
3 118
3 141
3 166
3 193
3 222
4 5
4 12
4 21
4 32
4 45
4 60
4 77
4 96
4 117
4 140
4 165
4 192
4 221
5 11
5 20
5 31
5 44
5 59...

output:

not smol

result:

ok not smol

Test #66:

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

input:

100 0

output:

0

result:

ok vertex cover of size 0

Test #67:

score: 0
Accepted
time: 2ms
memory: 3744kb

input:

222 960
55 144
6 148
20 22
28 208
54 106
108 154
19 150
18 21
17 158
55 90
94 117
37 132
84 220
8 40
2 176
65 134
175 181
90 161
10 191
13 221
13 22
48 98
1 220
48 75
37 165
104 196
63 79
99 169
176 203
180 207
32 37
39 220
8 30
87 208
39 139
94 119
57 169
21 51
24 80
169 184
71 82
37 207
51 151
26 ...

output:

not smol

result:

ok not smol

Test #68:

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

input:

222 1611
43 217
138 208
124 136
12 193
98 203
94 141
36 90
38 151
151 186
13 217
62 125
80 151
91 136
86 172
36 176
74 128
47 167
171 184
129 182
151 155
120 198
151 210
51 200
24 128
184 201
185 208
96 98
23 203
26 198
151 191
76 153
68 160
73 111
13 151
75 164
9 151
119 189
32 151
101 151
143 212
...

output:

not smol

result:

ok not smol

Test #69:

score: 0
Accepted
time: 87ms
memory: 4312kb

input:

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

output:

not smol

result:

ok not smol

Test #70:

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

input:

222 222
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
51 52
52 ...

output:

111
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175...

result:

ok vertex cover of size 111

Test #71:

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

input:

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

output:

37
1 7 13 19 25 31 37 43 49 55 61 67 73 79 85 91 97 103 109 115 121 127 133 139 145 151 157 163 169 175 181 187 193 199 205 211 217

result:

ok vertex cover of size 37

Test #72:

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

input:

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

output:

not smol

result:

ok not smol

Test #73:

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

input:

220 1034
1 2
1 3
1 4
1 5
1 8
1 9
1 10
1 11
1 12
1 14
1 15
1 16
1 17
1 18
1 19
1 20
2 4
2 8
2 9
2 10
2 12
2 14
2 15
2 16
2 17
2 18
2 19
2 20
3 5
3 8
3 15
4 5
4 8
4 10
4 15
4 16
4 18
4 19
5 6
5 8
5 9
5 10
5 11
5 12
5 13
5 14
5 15
5 16
5 17
5 19
5 20
6 8
7 8
7 19
8 9
8 10
8 12
8 14
8 15
8 16
8 17
8 18
...

output:

110
1 2 15 16 5 8 19 18 10 12 21 22 35 36 25 28 39 38 30 32 41 42 55 56 45 48 59 58 50 54 61 62 75 76 65 68 79 78 70 72 81 82 95 96 85 88 99 98 90 94 101 102 115 116 105 108 119 118 110 112 121 122 135 136 125 128 139 138 130 132 141 142 155 156 145 148 159 158 150 152 161 162 175 176 165 168 179 17...

result:

ok vertex cover of size 110

Test #74:

score: 0
Accepted
time: 2ms
memory: 3636kb

input:

200 664
1 2
1 3
1 8
1 10
1 15
1 21
1 22
1 24
1 27
1 35
1 38
1 40
1 50
2 3
2 17
2 18
2 19
2 32
2 43
2 46
3 5
3 7
3 10
3 29
3 34
3 36
3 37
3 38
3 44
4 7
4 9
4 14
4 15
4 29
4 30
4 33
4 41
4 47
5 7
5 19
5 22
5 34
5 35
5 38
5 42
6 27
7 15
7 21
7 27
7 29
7 35
7 38
7 43
7 47
7 50
8 29
8 40
8 46
9 29
9 31
1...

output:

100
1 2 3 4 35 27 7 8 10 11 38 29 19 31 34 44 21 22 23 42 25 28 30 36 47 51 52 53 54 85 77 57 58 60 61 72 79 88 81 69 94 71 73 92 75 78 80 86 84 97 101 102 103 104 135 127 107 108 110 111 138 129 119 131 134 144 121 122 123 142 125 128 130 136 147 151 152 153 154 185 177 157 158 160 161 188 179 169 ...

result:

ok vertex cover of size 100

Test #75:

score: 0
Accepted
time: 4ms
memory: 3660kb

input:

200 552
1 2
1 8
1 15
1 21
1 24
1 27
1 38
1 49
2 3
2 17
2 18
2 19
2 32
2 43
2 46
3 5
3 7
3 19
3 25
3 31
3 34
3 35
3 37
3 44
4 9
4 15
4 29
4 30
4 33
5 7
5 10
5 22
5 30
5 34
5 44
5 49
6 27
7 15
7 21
7 27
7 29
7 35
7 38
7 43
7 47
7 50
8 29
8 40
8 46
9 29
10 22
10 29
10 31
10 49
10 50
11 22
11 25
11 32
1...

output:

not smol

result:

ok not smol

Test #76:

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

input:

4 4
1 2
1 3
1 4
2 3

output:

2
1 2

result:

ok vertex cover of size 2

Test #77:

score: 0
Accepted
time: 3ms
memory: 3636kb

input:

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

output:

not smol

result:

ok not smol

Test #78:

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

input:

222 1895
11 67
39 74
52 134
48 204
78 156
103 191
32 37
130 197
33 35
50 173
30 45
28 203
81 127
138 206
20 94
96 147
98 137
137 158
139 216
11 77
15 34
9 17
25 216
71 126
1 40
8 134
179 212
135 168
71 89
30 75
97 154
170 175
38 198
28 208
34 39
85 89
33 160
31 83
133 213
87 208
64 200
49 136
85 169...

output:

not smol

result:

ok not smol

Test #79:

score: 0
Accepted
time: 2ms
memory: 3560kb

input:

222 101
191 214
139 141
44 48
85 156
141 148
8 113
159 221
107 119
73 160
45 214
70 161
59 78
81 123
42 119
38 43
21 187
81 207
19 53
34 180
10 118
30 222
34 196
21 144
168 206
38 213
33 177
175 190
100 140
96 175
200 221
17 76
44 105
19 125
79 124
13 107
87 91
132 148
14 205
66 88
22 210
15 152
28 ...

output:

57
26 113 118 12 13 58 152 17 18 19 20 21 22 197 28 219 222 31 177 34 38 119 205 44 214 52 87 57 59 63 64 65 66 70 71 73 168 79 81 85 199 97 98 100 101 131 181 127 148 141 154 171 191 175 183 221 202

result:

ok vertex cover of size 57

Test #80:

score: 0
Accepted
time: 3ms
memory: 3656kb

input:

222 314
21 74
81 180
26 123
106 155
12 197
158 188
32 54
27 134
9 193
191 206
73 158
5 73
40 193
67 89
129 143
39 213
141 159
6 182
143 164
107 201
47 123
104 130
191 209
149 177
10 21
96 144
107 206
3 38
165 195
58 198
188 204
40 182
133 205
15 208
84 123
5 24
70 120
78 118
44 128
19 201
127 167
72...

output:

not smol

result:

ok not smol

Test #81:

score: 0
Accepted
time: 4ms
memory: 3724kb

input:

222 397
90 99
80 217
79 198
56 104
140 185
202 213
129 195
169 181
20 72
27 81
70 106
55 88
2 22
145 221
162 208
27 66
32 119
29 55
91 124
97 161
59 74
155 162
98 170
52 187
14 207
7 149
10 86
147 162
185 207
100 112
30 36
58 64
65 151
152 191
119 201
38 216
23 220
9 111
30 105
122 140
121 176
12 62...

output:

not smol

result:

ok not smol

Test #82:

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

input:

222 351
32 156
28 72
80 83
175 222
117 156
142 222
28 113
136 154
53 56
93 99
29 73
112 175
129 151
3 12
36 77
3 127
63 123
140 164
109 162
17 115
134 173
25 137
1 48
86 107
61 70
191 207
6 68
76 109
24 204
9 25
149 158
77 82
84 136
61 148
12 18
71 110
67 141
95 187
113 186
13 162
60 169
51 110
77 1...

output:

not smol

result:

ok not smol

Test #83:

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

input:

222 362
133 149
15 173
26 96
91 196
74 218
153 208
63 135
46 65
35 205
36 182
82 182
130 164
121 127
34 205
127 201
68 74
2 87
187 214
113 221
7 33
7 68
81 187
22 32
122 125
122 148
28 84
99 100
13 36
95 115
175 199
67 180
2 167
58 129
133 170
9 83
9 103
79 80
9 100
40 79
67 144
197 219
41 146
35 48...

output:

105
1 2 3 4 155 6 7 8 9 64 11 68 34 207 15 16 154 18 19 169 32 93 24 129 96 27 28 35 41 36 37 130 39 40 66 75 44 51 46 47 80 50 52 87 54 55 56 57 58 59 178 99 101 63 67 125 123 141 72 73 76 77 187 182 86 193 151 164 138 92 94 95 100 172 137 106 108 213 211 113 136 118 120 121 122 205 127 220 170 139...

result:

ok vertex cover of size 105

Test #84:

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

input:

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

output:

111
1 4 3 10 8 11 17 18 15 19 23 22 25 27 28 31 34 36 38 41 40 43 47 46 49 53 52 58 56 59 61 62 66 67 68 69 75 76 78 79 80 84 85 90 89 91 92 94 102 98 99 103 105 107 109 110 112 118 116 117 121 124 125 127 128 131 133 134 135 139 141 144 148 146 147 151 155 154 159 158 162 163 165 167 169 170 172 17...

result:

ok vertex cover of size 111

Test #85:

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

input:

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

output:

111
1 2 4 12 11 9 17 18 15 19 20 23 25 26 27 36 32 33 37 38 42 44 45 48 50 51 53 55 57 60 61 66 65 69 68 72 75 77 78 82 80 83 85 86 87 91 95 94 97 99 100 103 106 108 109 113 112 115 119 117 121 125 126 130 132 129 133 135 136 142 140 141 148 146 150 151 152 156 157 158 160 163 164 168 170 171 173 17...

result:

ok vertex cover of size 111

Test #86:

score: 0
Accepted
time: 2ms
memory: 3636kb

input:

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

output:

111
1 4 6 7 11 10 13 14 15 22 20 21 25 27 30 34 33 35 40 39 42 43 44 45 49 53 54 55 57 60 61 66 64 67 69 70 73 74 78 79 81 83 88 86 90 91 94 95 102 98 101 103 107 106 109 114 111 117 116 120 121 126 124 130 129 131 137 134 138 140 141 142 145 147 150 154 153 155 157 160 162 163 167 166 169 173 172 1...

result:

ok vertex cover of size 111

Test #87:

score: 0
Accepted
time: 6ms
memory: 3664kb

input:

222 1164
107 130
176 216
154 215
72 76
17 210
76 180
15 200
14 93
46 157
88 93
57 96
90 209
95 167
66 132
20 212
142 188
143 219
38 40
37 65
55 114
14 131
43 93
75 76
93 195
7 127
14 102
93 123
183 221
132 200
57 134
114 117
93 162
89 93
41 93
119 142
129 172
103 138
32 57
134 155
23 143
51 112
35 8...

output:

not smol

result:

ok not smol

Test #88:

score: 0
Accepted
time: 6ms
memory: 3944kb

input:

222 12321
204 207
142 183
48 58
197 198
12 25
148 163
62 143
132 179
112 191
55 80
71 115
57 119
57 162
31 35
2 176
31 186
12 73
63 86
42 220
156 197
130 204
130 142
27 94
94 136
51 170
54 93
119 191
159 183
26 141
47 127
63 205
192 199
133 172
31 152
100 182
54 69
52 160
72 89
25 196
68 183
16 203
...

output:

111
1 2 3 76 143 6 7 8 9 91 152 12 13 14 67 16 17 18 54 21 97 23 24 25 26 27 160 46 85 169 142 92 188 35 36 37 103 40 191 158 45 47 48 70 105 51 198 53 57 56 58 114 60 202 204 64 94 72 101 71 73 133 98 80 138 165 208 86 89 95 96 217 100 102 192 167 108 109 220 115 136 135 186 121 187 132 130 183 150...

result:

ok vertex cover of size 111

Test #89:

score: 0
Accepted
time: 5ms
memory: 3744kb

input:

222 1091
33 135
47 179
110 133
182 217
139 157
47 183
122 142
155 217
202 214
16 82
7 98
66 205
46 178
103 196
26 92
74 91
13 175
26 57
4 202
26 182
85 217
129 183
145 217
108 175
8 215
9 122
26 55
95 195
8 93
179 220
66 169
98 122
14 217
20 156
18 62
2 217
118 142
47 94
173 214
134 187
3 192
72 110...

output:

not smol

result:

ok not smol

Test #90:

score: 0
Accepted
time: 3ms
memory: 3648kb

input:

126 579
27 46
58 92
24 58
21 90
7 30
24 32
43 74
53 58
81 115
16 67
27 56
2 120
40 103
25 99
50 90
109 113
48 73
2 115
2 104
4 83
53 110
81 94
23 56
20 118
18 38
58 72
64 101
98 107
48 118
50 83
85 90
45 58
4 90
4 50
55 118
8 70
23 38
18 89
38 82
70 116
38 91
58 123
44 58
18 80
49 118
29 40
58 119
5...

output:

not smol

result:

ok not smol

Test #91:

score: 0
Accepted
time: 2ms
memory: 3548kb

input:

13 29
5 12
1 13
5 13
6 10
1 12
3 4
2 13
4 13
6 8
2 4
9 12
4 10
2 6
10 11
7 8
10 12
2 12
11 13
9 10
4 8
7 11
3 8
5 11
4 9
6 11
1 2
9 11
1 10
11 12

output:

7
13 2 4 12 10 8 11

result:

ok vertex cover of size 7

Test #92:

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

input:

17 29
6 7
3 17
12 16
6 16
2 11
15 17
9 12
7 9
3 15
6 12
13 14
1 14
1 3
8 15
10 17
2 7
9 10
6 17
11 14
2 15
5 10
16 17
6 9
3 14
4 12
2 10
9 15
1 5
2 12

output:

9
1 5 2 17 12 6 15 9 14

result:

ok vertex cover of size 9

Test #93:

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

input:

19 36
6 13
8 9
14 15
2 8
13 18
3 7
16 19
11 13
4 18
1 13
5 10
10 13
5 13
8 15
2 3
7 11
10 18
4 17
11 14
6 15
16 18
10 12
12 13
3 5
1 9
1 15
9 13
3 16
1 16
2 17
6 8
12 19
14 17
3 10
8 16
12 15

output:

10
19 1 17 3 18 13 11 8 10 15

result:

ok vertex cover of size 10
English 繁體中文 简体中文

服务器时间: 2024-12-13 00:19:39 | 开源项目