QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#435696#8757. 图qzezAC ✓111ms162200kbC++142.2kb2024-06-08 21:06:102024-06-08 21:06:11

Judging History

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

  • [2024-06-08 21:06:11]
  • 评测
  • 测评结果：AC
  • 用时：111ms
  • 内存：162200kb
查看
  • [2024-06-08 21:06:10]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned ll;
const int N=1e5+10;
int T,n,m,s,t;
vector<int>to[N];
vector<vector<int>>ans;
int fa[N],cnt[N],siz[N];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void link(int x,int y,int w){
	x=find(x),y=find(y);
	if(x==y)cnt[x]+=w;
	else cnt[y]+=cnt[x]+w,siz[y]+=siz[x],fa[x]=y;
}
vector<int>stk;
bool dfs(int u,int fa=0){
	stk.push_back(u);
	if(u==t)return ans.push_back(stk),1;
	for(int v:to[u])if(v^fa){
		if(dfs(v,u))return 1;
	}
	stk.pop_back();
	return 0;
}
void solve(const vector<tuple<int,int,int>> &E,int k){
	if(k==1){
		auto [u,v,w]=E[0];
		s=u,t=v,ans={{u,v}};
		return;
	}
	iota(fa,fa+1+n,0);
	fill(cnt,cnt+1+n,0);
	fill(siz+1,siz+1+n,1);
	for(auto [u,v,w]:E)link(u,v,w);
	int rt=0,mx=0;
	for(int i=1;i<=n;i++)if(fa[i]==i&&siz[i]>1){
		int val=(cnt[i]-1)/(siz[i]-1)+1;
		if(val>mx)mx=val,rt=i;
	}
	// debug(E);
	vector<tuple<int,int,int>>ne,ret;
	for(auto [u,v,w]:E){
		if(find(u)==rt)ne.push_back({u,v,w});
	}
	iota(fa,fa+1+n,0);
	vector<pair<int,int>>cur;
	// debug(ne);
	for(auto [u,v,w]:ne){
		int x=find(u),y=find(v);
		if(x!=y){
			fa[x]=y;
			cur.push_back({u,v});
			if(w>1)ret.push_back({u,v,w-1});
		}else ret.push_back({u,v,w});
	}
	// debug(cur);
	solve(ret,k-1);
	for(auto [u,v]:cur){
		to[u].push_back(v),to[v].push_back(u);
	}
	stk.clear(),dfs(s);
	for(int i=1;i<=n;i++)to[i].clear();
}
void get(){
	scanf("%d%d",&n,&m);
	vector<tuple<int,int,int>>E(m);
	for(auto &[u,v,w]:E){
		scanf("%d%d",&u,&v),w=1;
		if(u>v)swap(u,v);
	}
	sort(all(E));
	int len=0;
	for(int i=1;i<E.size();i++){
		auto &[u1,v1,w1]=E[len];
		auto &[u2,v2,w2]=E[i];
		if(u1==u2&&v1==v2)w1++;
		else E[++len]=E[i];
	}
	E.resize(len+1);
	solve(E,(m-1)/(n-1)+1);
	printf("%d %d\n",s,t);
	for(const auto &x:ans){
		printf("%ld",x.size());
		for(int y:x)printf(" %d",y);
		puts("");
	}
}
int main(){
	for(scanf("%d",&T);T--;)get();
	return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 61ms
memory: 6488kb

input:

10000
2 20
1 2
1 2
2 1
1 2
1 2
2 1
1 2
2 1
1 2
1 2
1 2
1 2
2 1
1 2
1 2
2 1
1 2
1 2
1 2
2 1
2 20
2 1
2 1
2 1
2 1
2 1
1 2
1 2
1 2
1 2
2 1
1 2
1 2
2 1
1 2
1 2
2 1
1 2
1 2
2 1
1 2
2 20
1 2
2 1
1 2
1 2
2 1
2 1
1 2
1 2
2 1
2 1
1 2
1 2
1 2
1 2
2 1
1 2
1 2
1 2
2 1
2 1
2 20
1 2
2 1
2 1
1 2
1 2
1 2
2 1
1 2
2 ...

output:

1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
...

result:

ok Answer correct. (10000 test cases)

Test #2:

score: 0
Accepted
time: 47ms
memory: 6172kb

input:

10000
5 20
2 1
2 5
5 3
3 1
4 5
1 4
4 3
4 5
3 5
5 4
2 3
5 2
3 4
3 5
1 4
4 3
4 2
2 1
1 3
5 1
5 20
4 2
1 3
1 2
4 5
2 4
3 1
5 3
5 1
4 5
4 3
2 4
1 4
4 3
5 2
1 2
3 5
1 5
4 1
3 4
4 3
5 20
1 4
1 3
1 5
5 1
4 5
3 4
4 5
2 3
1 2
2 4
4 5
4 5
2 4
2 5
4 2
4 3
4 2
2 5
2 1
3 1
5 20
2 5
2 3
4 5
4 2
3 4
2 1
5 4
2 5
2 ...

output:

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

result:

ok Answer correct. (10000 test cases)

Test #3:

score: 0
Accepted
time: 51ms
memory: 6804kb

input:

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

output:

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

result:

ok Answer correct. (10000 test cases)

Test #4:

score: 0
Accepted
time: 17ms
memory: 6928kb

input:

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

output:

21 26
2 21 26
5 21 15 44 7 26
24 36
2 24 36
6 24 9 37 10 7 36
15 34
2 15 34
9 15 24 14 36 10 1 8 5 34
16 39
2 16 39
2 16 39
14 44
2 14 44
3 14 8 44
12 42
2 12 42
2 12 42
2 6
2 2 6
3 2 1 6
26 27
2 26 27
10 26 15 19 18 46 17 24 28 20 27
6 13
2 6 13
2 6 13
3 21
2 3 21
2 3 21
8 29
2 8 29
3 8 2 29
3 37
2...

result:

ok Answer correct. (2000 test cases)

Test #5:

score: 0
Accepted
time: 68ms
memory: 7220kb

input:

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

output:

24 41
2 24 41
2 24 41
2 24 41
4 24 33 22 41
4 24 33 22 41
5 24 22 33 21 41
11 24 22 27 20 30 17 38 15 44 19 41
10 24 22 20 27 15 39 18 42 19 41
10 24 20 14 39 15 29 16 33 18 41
3 24 17 41
6 24 14 25 12 15 41
4 24 13 15 41
4 24 11 14 41
8 24 7 43 8 38 9 13 41
9 24 7 38 8 14 10 12 11 41
9 24 7 27 6 11...

result:

ok Answer correct. (200 test cases)

Test #6:

score: 0
Accepted
time: 111ms
memory: 14476kb

input:

20
100 10000
77 84
14 62
84 5
4 67
99 44
54 18
39 53
58 88
32 3
61 19
76 14
28 72
92 34
20 1
14 66
98 25
53 99
55 40
13 70
42 62
32 41
93 14
74 66
92 62
42 12
94 35
26 65
82 85
100 34
79 47
87 59
4 92
46 4
77 63
17 62
32 23
46 76
61 26
89 41
10 18
17 64
55 61
89 42
8 71
75 89
2 81
9 63
42 32
23 34
7...

output:

50 89
2 50 89
2 50 89
2 50 89
4 50 79 48 89
6 50 78 49 79 48 89
6 50 78 48 84 47 89
10 50 71 49 78 48 79 46 99 47 89
8 50 67 48 78 47 79 46 89
8 50 67 48 76 47 79 46 89
8 50 62 49 66 48 67 46 89
10 50 61 49 63 47 71 46 67 44 89
8 50 61 49 62 47 67 44 89
8 50 59 48 63 47 67 44 89
8 50 54 47 62 45 67 ...

result:

ok Answer correct. (20 test cases)

Test #7:

score: 0
Accepted
time: 47ms
memory: 6616kb

input:

100
1000 1999
527 98
626 570
505 814
510 660
334 873
893 329
51 818
256 113
165 543
515 780
905 200
560 363
385 813
82 324
661 719
3 624
175 120
22 480
662 730
701 676
124 107
820 707
288 412
596 842
285 574
209 109
897 789
37 371
399 502
715 361
877 504
68 73
919 671
685 732
866 390
975 122
994 263...

output:

325 548
2 325 548
16 325 492 303 601 291 559 286 629 278 427 200 727 297 365 190 548
7 325 38 941 56 498 114 548
338 908
2 338 908
5 338 324 787 192 908
10 338 96 333 120 70 866 90 133 135 908
371 872
2 371 872
16 371 134 490 351 343 683 310 502 238 220 247 907 288 519 360 872
13 371 5 35 527 58 47 ...

result:

ok Answer correct. (100 test cases)

Test #8:

score: 0
Accepted
time: 20ms
memory: 6252kb

input:

1000
100 100
8 93
14 86
43 53
73 87
9 5
30 87
23 88
9 18
89 75
49 53
39 91
58 22
86 27
75 1
57 90
20 40
71 55
58 77
63 46
97 95
6 71
19 92
54 24
50 96
30 50
11 79
70 20
79 24
88 33
8 86
18 60
51 58
66 39
93 31
1 47
41 65
45 12
3 93
62 33
38 49
29 91
3 29
15 51
37 56
54 6
85 95
2 81
36 28
10 98
57 26...

output:

87 91
2 87 91
24 87 30 50 96 56 78 23 88 33 62 9 70 20 40 43 53 76 27 86 8 93 3 29 91
59 85
2 59 85
11 59 69 1 23 75 47 13 93 45 18 85
57 92
2 57 92
9 57 85 34 15 30 24 69 9 92
86 88
2 86 88
23 86 67 87 60 7 99 61 63 43 84 78 26 13 98 55 72 15 42 76 21 75 23 88
86 93
2 86 93
16 86 74 4 71 19 70 13 5...

result:

ok Answer correct. (1000 test cases)

Test #9:

score: 0
Accepted
time: 42ms
memory: 6196kb

input:

500
200 399
181 137
41 68
61 54
32 10
41 136
85 112
127 111
51 107
143 189
21 69
149 109
107 120
21 158
175 53
31 48
80 170
46 108
163 85
110 142
2 30
117 128
109 114
142 178
76 43
118 63
36 149
45 74
165 123
43 72
87 185
70 173
132 79
130 163
187 10
189 114
70 22
12 184
200 175
65 169
23 27
1 14
19...

output:

63 161
2 63 161
3 63 44 161
4 63 17 20 161
88 176
2 88 176
4 88 153 75 176
11 88 83 112 13 2 71 10 28 22 47 176
31 195
2 31 195
2 31 195
7 31 105 28 58 4 1 195
78 129
2 78 129
4 78 84 77 129
12 78 4 190 29 127 5 36 134 37 165 3 129
96 185
2 96 185
6 96 166 65 189 81 185
14 96 58 144 51 39 2 45 156 4...

result:

ok Answer correct. (500 test cases)

Test #10:

score: 0
Accepted
time: 55ms
memory: 6856kb

input:

2197
10 91
7 3
7 9
9 2
1 10
7 1
6 8
4 8
2 10
7 6
5 3
4 10
9 3
1 4
2 9
5 4
5 6
3 7
6 1
1 9
2 6
3 4
6 9
8 7
6 7
7 4
8 7
9 3
10 7
10 6
2 5
2 7
8 10
10 1
7 4
10 4
9 2
7 6
3 10
6 4
1 8
8 9
6 7
10 9
3 2
2 5
10 5
4 7
5 3
9 4
1 5
1 4
8 4
4 10
7 3
6 7
4 2
3 4
9 2
1 10
6 1
8 3
2 9
9 10
9 5
3 4
5 8
9 3
7 1
6 1...

output:

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

result:

ok Answer correct. (2197 test cases)

Test #11:

score: 0
Accepted
time: 55ms
memory: 6828kb

input:

1980
5 101
3 5
4 2
5 1
1 4
2 5
1 3
2 5
3 2
4 2
3 1
1 2
5 3
3 4
3 1
1 3
5 3
1 4
2 4
2 3
4 2
4 5
4 5
1 2
3 1
3 4
1 2
3 5
4 1
2 4
3 5
4 3
4 1
2 1
2 1
5 4
5 3
3 5
2 5
4 1
5 3
2 3
3 4
3 4
5 2
3 2
4 3
2 3
4 3
1 5
2 1
1 3
1 4
1 4
2 5
2 1
1 3
3 5
5 3
1 5
3 4
4 2
3 5
4 2
2 4
4 1
3 5
3 5
5 4
1 4
5 3
5 1
5 3
1...

output:

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

result:

ok Answer correct. (1980 test cases)

Test #12:

score: 0
Accepted
time: 72ms
memory: 17980kb

input:

1
100000 200000
34863 14128
21925 31963
32836 60679
64214 73508
66150 45252
9601 33518
33904 58681
94179 37263
91962 58845
44150 57595
75389 55087
95549 80645
35339 82663
93639 89411
91288 79966
6158 91046
34153 16675
38098 20451
49822 20670
34821 40807
67167 98424
75186 55129
47388 80048
47576 3327...

output:

38185 43084
2 38185 43084
25 38185 23612 27349 26761 76143 17920 61152 14605 91968 20228 46180 35252 97225 24583 37905 40727 32529 88264 26118 18172 64801 18014 92164 28291 43084
115 38185 12469 81873 2014 8704 91797 7411 3143 6252 11722 6274 38060 7579 19088 2821 27886 7850 63908 4792 4679 5778 917...

result:

ok Answer correct. (1 test case)

Test #13:

score: 0
Accepted
time: 27ms
memory: 13176kb

input:

1
100000 100000
83552 10530
25783 47244
84923 13681
21334 91194
91778 58467
19661 74982
25591 89762
59524 51208
87846 82043
11266 66764
81526 43233
68225 71631
59267 57074
14783 69153
4005 38103
10428 8712
16106 97817
65055 2008
87601 98588
44816 64853
13936 1829
49508 54999
20100 23207
3098 59651
5...

output:

96341 98907
2 96341 98907
345 96341 72670 52782 49299 90651 23827 13648 3956 91311 97263 95069 57333 2143 70159 96088 35960 83554 58328 13163 64578 31091 89040 12195 65342 58512 53861 9840 36601 10076 70053 77960 30181 34815 82437 30147 56697 48867 64924 18462 15661 536 40551 8666 17600 8527 86149 2...

result:

ok Answer correct. (1 test case)

Test #14:

score: 0
Accepted
time: 24ms
memory: 7232kb

input:

10
10000 10000
3288 319
1296 6368
8450 2814
7356 5128
7375 44
5324 3611
9164 7555
1308 5753
1325 8813
5264 796
602 9263
6701 6141
3612 4277
611 5775
8960 5850
4706 9495
7751 9401
8316 7060
8524 8033
7342 4672
2503 3504
4515 4649
3881 1881
2962 4138
9655 9539
9043 4098
2631 6216
1198 9724
6105 2802
6...

output:

9505 9651
2 9505 9651
232 9505 273 2102 9923 6352 4605 8229 6758 7732 3193 9153 630 9003 3590 7086 3758 993 1083 1728 7718 3799 9210 637 6313 1370 4640 8742 5115 7489 3606 5889 1188 360 8623 7461 9552 7254 7729 3015 7828 1312 15 6629 7183 6351 4959 1851 1354 8450 2814 4761 7234 1675 5290 3812 440 14...

result:

ok Answer correct. (10 test cases)

Test #15:

score: 0
Accepted
time: 19ms
memory: 6268kb

input:

1000
100 100
8 93
14 86
43 53
73 87
9 5
30 87
23 88
9 18
89 75
49 53
39 91
58 22
86 27
75 1
57 90
20 40
71 55
58 77
63 46
97 95
6 71
19 92
54 24
50 96
30 50
11 79
70 20
79 24
88 33
8 86
18 60
51 58
66 39
93 31
1 47
41 65
45 12
3 93
62 33
38 49
29 91
3 29
15 51
37 56
54 6
85 95
2 81
36 28
10 98
57 26...

output:

87 91
2 87 91
24 87 30 50 96 56 78 23 88 33 62 9 70 20 40 43 53 76 27 86 8 93 3 29 91
59 85
2 59 85
11 59 69 1 23 75 47 13 93 45 18 85
57 92
2 57 92
9 57 85 34 15 30 24 69 9 92
86 88
2 86 88
23 86 67 87 60 7 99 61 63 43 84 78 26 13 98 55 72 15 42 76 21 75 23 88
86 93
2 86 93
16 86 74 4 71 19 70 13 5...

result:

ok Answer correct. (1000 test cases)

Test #16:

score: 0
Accepted
time: 39ms
memory: 6492kb

input:

500
200 399
11 16
126 2
70 102
89 163
54 149
84 74
200 175
126 2
98 56
140 188
5 87
107 120
68 133
19 71
135 116
11 78
105 193
63 44
129 33
182 123
83 161
125 6
86 171
44 2
12 184
130 66
78 175
182 141
188 40
154 42
86 60
106 192
90 189
142 135
12 73
95 146
88 62
161 114
101 42
19 106
154 42
122 137...

output:

141 182
2 141 182
2 141 182
10 141 78 125 98 48 176 126 2 44 182
181 194
2 181 194
2 181 194
47 181 121 169 126 140 81 180 23 145 125 85 142 160 163 106 24 45 159 177 89 97 135 98 129 38 61 51 60 21 105 101 124 195 39 119 200 29 55 114 17 14 111 31 127 92 25 194
175 190
2 175 190
2 175 190
30 175 21...

result:

ok Answer correct. (500 test cases)

Test #17:

score: 0
Accepted
time: 41ms
memory: 6172kb

input:

2197
10 91
5 8
7 6
5 10
10 5
8 5
7 6
6 7
6 7
9 2
2 6
2 6
8 5
3 5
10 5
10 5
2 9
6 7
5 2
2 5
2 9
3 4
3 5
2 6
5 10
2 5
3 4
1 6
7 6
10 5
6 1
2 9
4 3
5 8
1 6
2 6
2 5
3 9
1 6
5 3
1 6
5 2
6 1
2 9
3 4
6 1
4 3
2 9
2 9
3 5
8 5
3 5
10 5
6 2
7 6
5 2
8 5
2 6
2 6
5 8
5 3
2 5
9 2
1 6
2 6
5 10
2 6
4 3
7 6
3 5
10 5
...

output:

3 9
2 3 9
4 3 5 2 9
4 3 5 2 9
4 3 5 2 9
4 3 5 2 9
4 3 5 2 9
4 3 5 2 9
4 3 5 2 9
4 3 5 2 9
4 3 5 2 9
4 3 5 2 9
6 10
2 6 10
2 6 10
2 6 10
2 6 10
2 6 10
2 6 10
2 6 10
2 6 10
2 6 10
2 6 10
2 6 10
3 6
2 3 6
2 3 6
2 3 6
2 3 6
2 3 6
2 3 6
2 3 6
2 3 6
2 3 6
2 3 6
2 3 6
8 9
2 8 9
2 8 9
2 8 9
2 8 9
2 8 9
2 8 ...

result:

ok Answer correct. (2197 test cases)

Test #18:

score: 0
Accepted
time: 47ms
memory: 6180kb

input:

1980
5 101
4 1
1 2
3 1
1 4
2 1
1 2
3 5
3 1
2 1
3 1
3 1
1 4
2 1
2 1
2 1
1 2
5 3
1 2
2 1
3 1
3 1
4 1
4 1
1 2
3 1
3 1
2 1
3 5
2 1
1 4
2 1
1 3
4 1
1 3
3 5
1 2
3 5
1 4
1 2
1 3
4 1
1 4
3 5
1 4
1 3
4 1
1 2
1 3
5 3
5 3
1 4
1 2
3 1
4 1
4 1
3 5
1 2
4 1
1 2
1 3
1 2
3 5
5 3
1 2
1 3
1 3
4 1
4 1
5 3
3 5
4 1
3 5
5...

output:

3 4
2 3 4
3 3 1 4
3 3 1 4
3 3 1 4
3 3 1 4
3 3 1 4
3 3 1 4
3 3 1 4
3 3 1 4
3 3 1 4
3 3 1 4
3 3 1 4
3 3 1 4
3 3 1 4
3 3 1 4
3 3 1 4
3 3 1 4
3 3 1 4
3 3 1 4
3 3 1 4
3 3 1 4
3 3 1 4
3 3 1 4
3 3 1 4
3 3 1 4
3 3 1 4
2 4
2 2 4
2 2 4
2 2 4
2 2 4
2 2 4
2 2 4
2 2 4
2 2 4
2 2 4
2 2 4
2 2 4
2 2 4
2 2 4
2 2 4
2 ...

result:

ok Answer correct. (1980 test cases)

Test #19:

score: 0
Accepted
time: 63ms
memory: 17712kb

input:

1
100000 200000
87045 64020
81145 29667
96830 91785
89750 28062
45195 59300
91075 91364
78904 20649
70802 2933
94952 13184
34881 9027
6909 45228
72094 87157
12710 6185
79492 76809
82773 25162
70583 95131
80195 23414
66965 46121
39034 27901
66559 13084
92952 38920
10715 65225
63505 2126
94217 79830
9...

output:

86782 95090
2 86782 95090
2 86782 95090
23 86782 21481 88426 73849 92296 77493 42784 52352 60774 64519 84919 29228 29773 83044 45988 2968 34470 72577 6636 77824 5009 74529 95090

result:

ok Answer correct. (1 test case)

Test #20:

score: 0
Accepted
time: 26ms
memory: 13184kb

input:

1
100000 100000
83552 10530
25783 47244
84923 13681
21334 91194
91778 58467
19661 74982
25591 89762
59524 51208
87846 82043
11266 66764
81526 43233
68225 71631
59267 57074
14783 69153
4005 38103
10428 8712
16106 97817
65055 2008
87601 98588
44816 64853
13936 1829
49508 54999
20100 23207
3098 59651
5...

output:

96341 98907
2 96341 98907
345 96341 72670 52782 49299 90651 23827 13648 3956 91311 97263 95069 57333 2143 70159 96088 35960 83554 58328 13163 64578 31091 89040 12195 65342 58512 53861 9840 36601 10076 70053 77960 30181 34815 82437 30147 56697 48867 64924 18462 15661 536 40551 8666 17600 8527 86149 2...

result:

ok Answer correct. (1 test case)

Test #21:

score: 0
Accepted
time: 24ms
memory: 6972kb

input:

10
10000 10000
3288 319
1296 6368
8450 2814
7356 5128
7375 44
5324 3611
9164 7555
1308 5753
1325 8813
5264 796
602 9263
6701 6141
3612 4277
611 5775
8960 5850
4706 9495
7751 9401
8316 7060
8524 8033
7342 4672
2503 3504
4515 4649
3881 1881
2962 4138
9655 9539
9043 4098
2631 6216
1198 9724
6105 2802
6...

output:

9505 9651
2 9505 9651
232 9505 273 2102 9923 6352 4605 8229 6758 7732 3193 9153 630 9003 3590 7086 3758 993 1083 1728 7718 3799 9210 637 6313 1370 4640 8742 5115 7489 3606 5889 1188 360 8623 7461 9552 7254 7729 3015 7828 1312 15 6629 7183 6351 4959 1851 1354 8450 2814 4761 7234 1675 5290 3812 440 14...

result:

ok Answer correct. (10 test cases)

Test #22:

score: 0
Accepted
time: 35ms
memory: 7512kb

input:

20
1000 9991
608 923
654 599
933 66
70 763
831 458
568 444
779 393
190 673
732 818
283 551
630 583
95 237
278 681
343 514
190 613
96 150
408 366
995 927
361 632
97 217
460 112
838 136
975 614
897 726
181 42
164 323
243 512
188 849
530 636
822 817
259 623
182 776
442 562
911 462
392 313
143 234
669 1...

output:

730 982
2 730 982
2 730 982
2 730 982
2 730 982
2 730 982
2 730 982
2 730 982
2 730 982
2 730 982
2 730 982
37 730 290 859 511 51 62 508 384 498 342 953 298 153 548 172 97 760 692 458 371 973 657 565 845 321 65 588 69 156 263 100 828 677 393 390 19 982
780 908
2 780 908
2 780 908
2 780 908
2 780 908...

result:

ok Answer correct. (20 test cases)

Test #23:

score: 0
Accepted
time: 59ms
memory: 7368kb

input:

422
3 733
3 1
2 1
1 2
1 3
3 1
3 1
2 3
2 3
1 3
1 3
2 1
2 3
2 3
3 1
3 1
2 3
3 2
2 1
1 3
2 3
2 1
2 1
3 1
2 3
2 1
2 3
2 3
2 3
2 3
3 1
2 1
2 3
1 2
2 1
2 1
3 2
3 1
3 1
1 2
3 2
2 3
1 3
2 1
2 3
1 3
1 2
3 1
3 1
2 3
1 2
1 3
1 2
2 1
3 1
1 3
3 1
3 1
3 2
1 3
3 1
3 1
3 1
3 1
2 1
2 1
1 2
1 3
3 1
1 3
3 1
1 3
3 2
1 ...

output:

2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 2 3
2 ...

result:

ok Answer correct. (422 test cases)

Test #24:

score: 0
Accepted
time: 63ms
memory: 11300kb

input:

46
6 3725
3 4
6 4
3 5
6 5
4 6
6 5
2 6
2 6
5 4
4 3
1 6
3 5
6 4
6 3
3 4
2 3
1 6
2 6
5 2
4 3
5 2
6 2
2 6
6 1
1 6
3 5
3 4
3 1
5 4
1 3
1 4
6 2
1 2
5 3
3 6
6 5
4 6
1 6
4 1
4 6
1 5
1 2
6 5
3 4
4 6
1 4
2 4
4 5
3 5
6 4
4 6
1 2
3 2
4 6
2 4
3 2
6 3
4 2
3 4
2 3
4 5
6 5
6 4
3 5
4 1
1 3
2 3
1 3
5 3
5 1
5 1
5 1
5 ...

output:

3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 ...

result:

ok Answer correct. (46 test cases)

Test #25:

score: 0
Accepted
time: 38ms
memory: 6828kb

input:

199
788 1339
53 304
46 671
763 311
642 211
746 529
591 661
87 400
252 103
311 359
111 320
437 445
435 406
351 666
202 564
781 713
203 151
576 587
197 458
280 577
26 256
118 9
664 554
111 359
112 267
151 36
578 740
631 166
26 80
200 327
55 289
570 342
202 243
714 322
751 763
288 123
340 752
73 426
26...

output:

3 388
2 3 388
2 3 388
220 511
2 220 511
4 220 465 154 511
28 220 41 266 37 616 21 52 252 14 312 39 752 25 199 7 427 74 51 821 31 90 6 816 58 623 36 84 511
18 753
2 18 753
2 18 753
1 415
2 1 415
26 56
2 26 56
2 26 56
4 26 47 25 56
4 26 33 23 56
6 26 27 25 37 22 56
9 26 24 31 22 36 21 41 20 56
8 26 20...

result:

ok Answer correct. (199 test cases)

Test #26:

score: 0
Accepted
time: 105ms
memory: 162200kb

input:

1
100 200000
31 47
24 16
52 62
47 68
75 53
24 73
31 98
23 30
19 87
3 53
26 87
64 93
32 98
39 94
90 56
90 89
15 17
62 57
9 83
35 56
20 88
19 10
59 32
75 22
69 59
97 5
38 71
24 50
47 48
31 47
1 30
14 76
46 4
23 46
3 19
27 74
49 31
11 17
32 53
43 71
7 87
42 72
90 20
100 8
98 64
23 72
60 20
10 27
78 93
...

output:

50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 75
2 50 7...

result:

ok Answer correct. (1 test case)

Test #27:

score: 0
Accepted
time: 45ms
memory: 39328kb

input:

1
11 199991
2 10
4 1
2 5
6 1
9 11
5 2
1 10
10 4
5 7
1 4
4 8
7 3
6 3
7 2
1 7
7 6
6 3
10 6
9 10
7 4
1 4
5 4
2 1
3 11
4 11
9 3
7 6
9 2
7 9
4 6
5 7
10 1
3 1
7 2
11 9
11 2
9 8
1 8
5 11
3 2
6 5
10 11
11 3
4 7
4 1
5 3
7 6
8 9
3 5
7 8
3 2
7 5
10 9
8 2
10 6
9 11
10 4
11 7
10 3
11 1
6 2
1 5
9 2
11 1
4 8
8 7
6...

output:

6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 6 7
2 ...

result:

ok Answer correct. (1 test case)

Test #28:

score: 0
Accepted
time: 34ms
memory: 23948kb

input:

1
11 199991
1 11
3 8
3 8
7 3
9 11
3 8
2 3
1 11
3 7
7 4
7 3
8 3
9 11
11 1
9 8
10 8
3 2
11 9
1 11
9 8
4 6
3 2
3 7
7 3
11 9
11 1
3 7
6 4
7 5
2 3
6 4
4 6
8 3
5 7
3 7
5 7
5 7
3 8
5 7
11 9
4 7
9 8
10 8
1 11
4 6
9 8
8 9
2 3
7 4
6 4
2 3
7 4
11 9
3 2
8 9
11 1
9 8
2 3
3 8
7 4
7 4
8 9
4 7
11 1
8 10
3 8
10 8
6 ...

output:

9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2 9 11
2...

result:

ok Answer correct. (1 test case)

Test #29:

score: 0
Accepted
time: 37ms
memory: 16792kb

input:

1
101 199901
88 63
18 41
58 27
11 39
70 51
24 81
48 98
54 83
16 59
32 91
94 46
64 45
16 80
26 97
93 35
66 42
21 42
2 50
86 55
4 68
85 50
50 42
57 66
37 8
1 85
70 51
18 16
52 16
56 96
24 81
66 90
32 91
77 34
55 86
83 44
42 66
67 1
23 100
56 96
10 73
1 85
68 85
75 23
39 76
41 18
17 1
41 47
80 83
16 80...

output:

80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 83
2 80 8...

result:

ok Answer correct. (1 test case)

Test #30:

score: 0
Accepted
time: 82ms
memory: 37380kb

input:

16
147 29384
50 25
83 135
61 141
33 65
33 70
64 130
39 43
5 142
64 58
45 68
55 115
34 110
75 42
136 71
89 53
65 126
125 44
40 135
29 15
6 120
111 107
132 147
86 125
28 76
41 79
33 94
19 65
45 99
16 69
133 106
136 71
83 34
93 70
77 22
62 72
51 27
111 70
125 102
39 99
113 84
102 61
53 8
81 83
63 105
3...

output:

73 134
2 73 134
2 73 134
2 73 134
2 73 134
2 73 134
4 73 119 72 134
4 73 119 72 134
4 73 107 72 134
6 73 107 72 112 71 134
6 73 105 72 111 71 134
10 73 105 72 111 71 126 69 128 70 134
8 73 94 72 105 71 122 70 134
6 73 94 72 105 70 134
8 73 94 72 101 71 105 70 134
6 73 94 71 102 69 134
6 73 93 70 102...

result:

ok Answer correct. (16 test cases)
English 繁體中文 简体中文

Server Time: 2024-12-04 20:03:34 | OpenSource Project