QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#784327#8757. 图hotdogsellerAC ✓509ms91632kbC++142.8kb2024-11-26 14:38:062024-11-26 14:38:08

Judging History

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

  • [2024-11-26 14:38:08]
  • 评测
  • 测评结果：AC
  • 用时：509ms
  • 内存：91632kb
查看
  • [2024-11-26 14:38:06]
  • 提交

answer

#include<bits/stdc++.h>

#define maxn 200008
#define pii pair<int,int>
#define int long long

using namespace std;

inline int read(){
    int lre=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-'){
            f=-1;
        }
        c=getchar();
    }
    while(isdigit(c)){
        lre=(lre<<3)+(lre<<1)+(c-'0');
        c=getchar();
    }
    return lre*f;
}

inline int f(int a,int b){
	return (a<<32)|b;
} 

int T;
int n,m,s,t;
unordered_map<int,set<int> > ga[maxn];
unordered_map<int,int> mp;

void add(int u,int v,int y){
	mp[f(u,v)]++;
	ga[u][y].insert(v);
}

void del(int u,int v,int y){
	mp[f(u,v)]--;
	if(mp[f(u,v)]==0)ga[u][y].erase(ga[u][y].find(v));
}

int cnt=0;
unordered_map<int,unordered_map<int,int> > root;

inline int f_f(int x,int y){
	if(root[y][x]==0)root[y][x]=x;
	if(root[y][x]!=x){
		root[y][x]=f_f(root[y][x],y);
	}
	return root[y][x];
} 

void merge(int u,int v,int y){
	if(root[y][u]==0)root[y][u]=u;
	if(root[y][v]==0)root[y][v]=v;
	root[y][f_f(u,y)]=f_f(v,y);
}

bool okay=false;
vector<int> v;
bool visited[maxn];

void dfs(int x,int goal,int y){
//	cout<<"x="<<x<<endl;
	v.push_back(x);visited[x]=true;
	if(x==goal){
		printf("%lld ",v.size());
		for(int i:v){
			printf("%lld ",i);
		} 
		putchar('\n');
		okay=true;
	}else{
		set<int>::iterator it;
		for(it=ga[x][y].begin();it!=ga[x][y].end();it++){
			int v=*it;
			if(visited[v])continue;
		//	cout<<x<<"->"<<v<<endl;
			dfs(v,goal,y);
			if(okay){
				del(x,v,y);del(v,x,y);
				break;
			}
		}
	}
	v.pop_back();visited[x]=false;
}

void solve(){
	n=read();m=read();
//	cout<<"new!!!!!!!!!!!!!!!!!!!!!n="<<n<<" m="<<m<<"!!!!!"<<endl;
	mp.clear();cnt=0;root.clear(); 
	for(int i=1;i<=n;i++){
		ga[i].clear(); 
	}
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
	//	cout<<"fu="<<f_f(u,cnt)<<" fv="<<f_f(v,cnt)<<endl; 
		if(cnt==0||f_f(u,cnt)==f_f(v,cnt)){
		//	cout<<"new!"<<endl; 
			cnt++;merge(u,v,cnt);
			add(u,v,cnt);add(v,u,cnt);
		}else{
			int l=1,r=cnt,mid,ind;
			while(l<=r){
				mid=l+r>>1;
				if(f_f(u,mid)==f_f(v,mid)){
					l=mid+1;
				}else{
					ind=mid;
					r=mid-1;
				}
			}
			merge(u,v,ind);
			add(u,v,ind);add(v,u,ind);
		}
	//	if(i%10000==0){
	//		cout<<"i="<<i<<" time="<<clock()<<"ms"<<endl;
	//	}
	}
//	cout<<"cnt="<<cnt<<endl; 
	for(int i=1;i<=n;i++){
		if(f_f(i,cnt)!=i){
			s=i;t=f_f(i,cnt);
			break;
		}
	}
//	cout<<"res:";
	printf("%lld %lld\n",s,t);
	int k=(m+n-2)/(n-1);
//	cout<<"k="<<k<<endl;
	for(int i=1;i<=k;i++){
	//	cout<<"No "<<i<<".";
		okay=false;
		dfs(s,t,i);
	}
}

signed main(){
	
//	freopen("19.in","r",stdin);
	
	memset(visited,0,sizeof(visited));
	
	T=read();
	while(T--){
	//	cout<<"t="<<T<<endl;
		solve();
	} 
	
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 114ms
memory: 14848kb

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:

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

result:

ok Answer correct. (10000 test cases)

Test #2:

score: 0
Accepted
time: 136ms
memory: 15144kb

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:

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

result:

ok Answer correct. (10000 test cases)

Test #3:

score: 0
Accepted
time: 119ms
memory: 14812kb

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:

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

result:

ok Answer correct. (10000 test cases)

Test #4:

score: 0
Accepted
time: 64ms
memory: 14876kb

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:

2 15
8 2 17 31 33 3 28 44 15 
2 2 15 
7 10
6 7 36 24 9 37 10 
2 7 10 
15 24
9 15 34 5 8 1 10 36 14 24 
2 15 24 
4 19
17 4 10 31 1 47 24 36 28 22 3 13 21 26 42 14 49 19 
2 4 19 
20 11
4 20 47 35 11 
2 20 11 
1 45
11 1 24 3 31 12 41 22 9 30 19 45 
2 1 45 
1 13
3 1 2 13 
2 1 13 
18 19
7 18 46 42 36 26 ...

result:

ok Answer correct. (2000 test cases)

Test #5:

score: 0
Accepted
time: 197ms
memory: 15164kb

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:

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

result:

ok Answer correct. (200 test cases)

Test #6:

score: 0
Accepted
time: 312ms
memory: 17492kb

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:

5 6
14 5 84 77 63 76 14 62 42 89 20 99 48 91 6 
7 5 64 41 87 60 67 6 
12 5 66 96 91 72 46 98 31 76 94 69 6 
12 5 73 39 68 71 72 98 36 63 65 74 6 
11 5 47 17 76 20 42 26 78 33 95 6 
12 5 18 96 29 27 76 14 57 62 71 91 6 
12 5 31 65 86 15 10 13 43 99 88 80 6 
9 5 41 77 43 46 1 49 40 6 
14 5 29 36 98 30...

result:

ok Answer correct. (20 test cases)

Test #7:

score: 0
Accepted
time: 196ms
memory: 15632kb

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:

2 50
7 2 316 806 355 20 721 50 
52 2 361 111 758 966 773 539 479 541 257 684 483 185 866 910 515 571 724 450 216 614 552 757 26 902 429 57 716 598 876 90 315 972 546 312 703 756 968 278 313 999 820 569 89 357 407 67 453 937 517 532 50 
2 2 50 
1 945
10 1 411 850 668 346 821 513 813 746 945 
27 1 258...

result:

ok Answer correct. (100 test cases)

Test #8:

score: 0
Accepted
time: 65ms
memory: 14900kb

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:

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

result:

ok Answer correct. (1000 test cases)

Test #9:

score: 0
Accepted
time: 178ms
memory: 15268kb

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:

11 27
4 11 16 23 27 
20 11 144 37 192 106 17 20 160 157 14 114 161 44 2 26 64 167 164 10 27 
2 11 27 
2 71
25 2 97 105 127 43 95 139 100 3 185 98 121 173 191 167 120 4 31 124 57 33 64 128 10 71 
26 2 13 197 67 100 177 159 138 24 27 25 162 83 88 176 50 89 78 161 127 142 125 147 133 193 71 
2 2 71 
8 ...

result:

ok Answer correct. (500 test cases)

Test #10:

score: 0
Accepted
time: 158ms
memory: 14884kb

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:

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

result:

ok Answer correct. (2197 test cases)

Test #11:

score: 0
Accepted
time: 160ms
memory: 15244kb

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:

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

result:

ok Answer correct. (1980 test cases)

Test #12:

score: 0
Accepted
time: 509ms
memory: 91632kb

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:

9 18414
96 9 9000 62036 46824 26853 86004 54073 77915 21490 74029 14261 44446 80790 53921 2193 33749 67962 93406 93623 27930 59201 78549 95648 34913 96558 27192 42935 75546 81874 52621 28259 18621 44600 45122 70535 35348 56067 76788 53294 53061 69741 982 40185 77495 19891 64549 81595 21913 26848 896...

result:

ok Answer correct. (1 test case)

Test #13:

score: 0
Accepted
time: 163ms
memory: 56488kb

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:

6329 40770
345 6329 44895 90140 65220 35185 10448 26774 12536 25433 55214 16739 70994 49742 27871 98650 44313 86479 36933 31407 16557 67002 49024 25876 23132 86149 8527 17600 8666 40551 536 15661 18462 64924 48867 56697 30147 82437 34815 30181 77960 70053 10076 36601 9840 53861 58512 65342 12195 890...

result:

ok Answer correct. (1 test case)

Test #14:

score: 0
Accepted
time: 119ms
memory: 19152kb

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:

9835 1804
232 9835 4068 1154 9529 6277 1508 5429 8430 2463 2493 7483 5292 3293 4445 9137 850 209 4927 4532 2843 7355 3821 9959 5172 7757 9784 124 7600 3934 6099 8462 9123 1082 6951 3737 4377 3278 8400 9934 6894 7423 2557 8434 5654 9954 4690 2558 8132 9491 1031 1982 7333 2017 1224 788 3428 7742 1812 ...

result:

ok Answer correct. (10 test cases)

Test #15:

score: 0
Accepted
time: 60ms
memory: 15184kb

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:

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

result:

ok Answer correct. (1000 test cases)

Test #16:

score: 0
Accepted
time: 162ms
memory: 15016kb

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:

176 126
10 176 48 98 125 78 141 182 44 2 126 
2 176 126 
2 176 126 
92 127
47 92 25 194 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 
2 92 127 
2 92 127 
175 190
30 175 21 88 10 130 22 177...

result:

ok Answer correct. (500 test cases)

Test #17:

score: 0
Accepted
time: 138ms
memory: 15232kb

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 5
2 3 5 
2 3 5 
4 3 9 2 5 
2 3 5 
2 3 5 
2 3 5 
2 3 5 
2 3 5 
2 3 5 
2 3 5 
2 3 5 
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 
6 3
2 6 3 
2 6 3 
2 6 3 
2 6 3 
2 6 3 
2 6 3 
2 6 3 
2 6 3 
2 6 3 
2 6 3 
2 6 3 
9 3
2 9 3 
2 9 3 
4 9 8 7 3 
2 9 3 
2 9 3...

result:

ok Answer correct. (2197 test cases)

Test #18:

score: 0
Accepted
time: 144ms
memory: 14968kb

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:

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

result:

ok Answer correct. (1980 test cases)

Test #19:

score: 0
Accepted
time: 397ms
memory: 79876kb

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:

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

result:

ok Answer correct. (1 test case)

Test #20:

score: 0
Accepted
time: 164ms
memory: 56656kb

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:

6329 40770
345 6329 44895 90140 65220 35185 10448 26774 12536 25433 55214 16739 70994 49742 27871 98650 44313 86479 36933 31407 16557 67002 49024 25876 23132 86149 8527 17600 8666 40551 536 15661 18462 64924 48867 56697 30147 82437 34815 30181 77960 70053 10076 36601 9840 53861 58512 65342 12195 890...

result:

ok Answer correct. (1 test case)

Test #21:

score: 0
Accepted
time: 120ms
memory: 19220kb

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:

9835 1804
232 9835 4068 1154 9529 6277 1508 5429 8430 2463 2493 7483 5292 3293 4445 9137 850 209 4927 4532 2843 7355 3821 9959 5172 7757 9784 124 7600 3934 6099 8462 9123 1082 6951 3737 4377 3278 8400 9934 6894 7423 2557 8434 5654 9954 4690 2558 8132 9491 1031 1982 7333 2017 1224 788 3428 7742 1812 ...

result:

ok Answer correct. (10 test cases)

Test #22:

score: 0
Accepted
time: 227ms
memory: 17160kb

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:

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

result:

ok Answer correct. (20 test cases)

Test #23:

score: 0
Accepted
time: 201ms
memory: 15720kb

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:

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

result:

ok Answer correct. (422 test cases)

Test #24:

score: 0
Accepted
time: 292ms
memory: 19080kb

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:

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

result:

ok Answer correct. (46 test cases)

Test #25:

score: 0
Accepted
time: 184ms
memory: 16276kb

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
9 3 70 355 247 330 218 376 701 388 
2 3 388 
266 162
19 266 201 396 634 65 101 867 723 593 297 610 775 841 875 446 776 261 386 162 
28 266 509 391 341 658 591 312 200 163 447 371 454 402 438 816 31 766 351 804 671 857 94 753 796 735 726 285 162 
2 266 162 
5 707
20 5 15 192 80 135 450 620 108 ...

result:

ok Answer correct. (199 test cases)

Test #26:

score: 0
Accepted
time: 464ms
memory: 60424kb

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:

94 85
12 94 39 12 30 23 64 98 32 53 75 84 85 
12 94 49 84 74 62 79 65 100 99 38 63 85 
16 94 78 91 12 58 74 57 25 20 5 99 62 60 81 26 85 
10 94 16 49 1 75 46 20 17 30 85 
10 94 31 89 78 73 37 32 95 30 85 
12 94 18 3 92 99 14 37 78 47 8 95 85 
2 94 85 
10 94 38 30 1 15 89 34 32 11 85 
8 94 36 13 95 6...

result:

ok Answer correct. (1 test case)

Test #27:

score: 0
Accepted
time: 428ms
memory: 62824kb

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:

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

result:

ok Answer correct. (1 test case)

Test #28:

score: 0
Accepted
time: 427ms
memory: 62848kb

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

result:

ok Answer correct. (1 test case)

Test #29:

score: 0
Accepted
time: 431ms
memory: 59732kb

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:

68 85
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 85 
2 68 8...

result:

ok Answer correct. (1 test case)

Test #30:

score: 0
Accepted
time: 419ms
memory: 54112kb

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:

146 44
12 146 117 55 22 64 83 34 110 61 102 125 44 
15 146 73 58 83 99 143 13 70 128 132 90 19 76 55 44 
16 146 116 29 6 81 87 95 64 85 99 133 40 76 17 107 44 
14 146 76 84 19 6 17 21 85 99 32 42 88 80 44 
38 146 78 49 21 119 71 9 138 1 42 99 24 32 17 96 108 35 106 111 84 92 130 85 11 5 18 101 54 53...

result:

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

Server Time: 2024-12-04 19:19:00 | OpenSource Project