QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#438661#8757. 图CrysflyAC ✓55ms46160kbC++171.9kb2024-06-10 21:31:332024-06-10 21:31:34

Judging History

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

  • [2024-06-10 21:31:34]
  • 评测
  • 测评结果:AC
  • 用时:55ms
  • 内存:46160kb
  • [2024-06-10 21:31:33]
  • 提交

answer

// what is matter? never mind. 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
//#define int long long
#define ull unsigned long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 500005
#define inf 0x3f3f3f3f

int n,m,k;

struct ufs{
	vi fa;
	void init(int n){
		fa.resize(n+1);
		For(i,0,n)fa[i]=i;
	}
	int gf(int x){
		while(x!=fa[x])x=fa[x]=fa[fa[x]];
		return x;
	}
	bool chk(int u,int v){
		return gf(u)==gf(v);
	}
	void mg(int u,int v){
		fa[gf(u)]=gf(v);
	}
}U[maxn];
vector<pii>buc[maxn];
int resu,resv;
vi e[maxn];

int fa[maxn];
void dfs(int u,int pa){
	fa[u]=pa;
	for(int v:e[u])if(v!=pa)dfs(v,u);
}


void work()
{
	n=read(),m=read();
	k=(m+n-2)/(n-1);
	For(i,1,k) U[i].init(n),buc[i].clear();
	For(i,1,m){
		int u=read(),v=read();
		int p=0;
		Rep(j,18,0)
			if(p+(1<<j)<=k && U[p+(1<<j)].chk(u,v))
				p+=(1<<j);
		p+=1;
		if(p<=k) U[p].mg(u,v),buc[p].pb(mkp(u,v));
		if(p>=k) resu=u,resv=v;
	}
	cout<<resv<<" "<<resu<<"\n";
	For(i,1,k){
		For(u,1,n) e[u].clear(),fa[u]=0;
		for(auto [u,v]:buc[i]) e[u].pb(v),e[v].pb(u);//cout<<"add "<<u<<" "<<v<<"\n";
		dfs(resu,0);
		vi o;
		for(int x=resv;x;x=fa[x]) o.pb(x);
		cout<<o.size()<<" ";
		for(int x:o)cout<<x<<" ";
		cout<<"\n";
	}
}

signed main()
{
	int T=read();
	while(T--)work();
	return 0;
}
/*
*/

詳細信息

Test #1:

score: 100
Accepted
time: 55ms
memory: 40420kb

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

result:

ok Answer correct. (10000 test cases)

Test #2:

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

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:

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

result:

ok Answer correct. (10000 test cases)

Test #3:

score: 0
Accepted
time: 36ms
memory: 39888kb

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

result:

ok Answer correct. (10000 test cases)

Test #4:

score: 0
Accepted
time: 12ms
memory: 39832kb

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:

38 21
4 38 34 41 21 
2 38 21 
10 7
6 10 37 9 24 36 7 
2 10 7 
26 23
13 26 43 3 28 40 8 1 10 36 14 24 21 23 
2 26 23 
16 39
2 16 39 
2 16 39 
11 37
8 11 35 19 17 50 43 12 37 
2 11 37 
46 38
11 46 3 31 12 41 22 9 30 19 45 38 
2 46 38 
11 3
10 11 32 22 15 31 7 13 2 6 3 
2 11 3 
17 46
9 17 24 28 20 27 2...

result:

ok Answer correct. (2000 test cases)

Test #5:

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

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:

38 31
7 38 27 22 15 30 16 31 
17 38 10 4 2 8 36 47 1 27 6 24 23 34 33 25 32 31 
10 38 17 29 50 30 27 34 43 47 31 
9 38 48 17 29 24 7 13 30 31 
10 38 2 37 49 9 29 40 32 5 31 
6 38 37 6 25 1 31 
3 38 43 31 
8 38 8 43 6 22 33 35 31 
8 38 8 14 45 47 10 41 31 
8 38 3 14 11 41 22 20 31 
5 38 15 29 23 31 
...

result:

ok Answer correct. (200 test cases)

Test #6:

score: 0
Accepted
time: 29ms
memory: 39260kb

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:

61 39
11 61 26 4 92 62 42 89 20 99 53 39 
3 61 69 39 
14 61 73 19 22 31 98 46 72 91 96 66 25 52 39 
2 61 39 
10 61 11 49 44 88 100 47 17 69 39 
23 61 93 15 28 43 29 27 76 14 100 73 4 40 99 44 63 12 80 20 88 79 9 39 
10 61 12 48 13 10 15 86 65 31 39 
15 61 43 46 1 49 57 99 88 16 87 69 47 93 75 39 
11...

result:

ok Answer correct. (20 test cases)

Test #7:

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

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:

97 183
14 97 786 660 510 629 645 256 113 216 368 101 447 906 183 
19 97 732 253 946 703 756 968 278 313 999 820 569 89 886 798 548 643 942 183 
2 97 183 
933 906
8 933 39 197 937 924 943 48 906 
28 933 311 648 853 559 464 960 491 268 830 691 339 87 163 778 529 614 774 304 692 827 443 369 206 307 924...

result:

ok Answer correct. (100 test cases)

Test #8:

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

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:

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

result:

ok Answer correct. (1000 test cases)

Test #9:

score: 0
Accepted
time: 21ms
memory: 39376kb

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:

125 98
15 125 78 175 200 79 80 170 188 142 110 104 59 75 24 98 
20 125 13 198 17 20 160 157 14 116 178 61 186 45 132 190 150 53 189 90 98 
2 125 98 
102 83
16 102 107 167 120 4 31 124 57 33 64 128 10 28 13 112 83 
12 102 172 87 132 127 161 78 89 50 176 88 83 
2 102 83 
7 28
10 7 178 25 170 75 140 17...

result:

ok Answer correct. (500 test cases)

Test #10:

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

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:

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

result:

ok Answer correct. (2197 test cases)

Test #11:

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

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 1
3 3 5 1 
2 3 1 
2 3 1 
2 3 1 
2 3 1 
2 3 1 
4 3 5 4 1 
3 3 4 1 
4 3 5 2 1 
3 3 2 1 
3 3 5 1 
3 3 2 1 
2 3 1 
3 3 4 1 
2 3 1 
3 3 4 1 
4 3 5 4 1 
3 3 5 1 
3 3 4 1 
3 3 5 1 
2 3 1 
4 3 5 2 1 
2 3 1 
2 3 1 
2 3 1 
2 3 1 
2 3
3 2 1 3 
2 2 3 
2 2 3 
4 2 5 1 3 
4 2 5 1 3 
3 2 5 3 
2 2 3 
4 2 5 1 3 
2 ...

result:

ok Answer correct. (1980 test cases)

Test #12:

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

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:

38060 6274
119 38060 2439 67896 57981 22217 38403 79778 13049 37948 44042 84291 18168 19272 63996 46553 1772 11981 91968 14605 61152 40404 81946 60074 95106 8693 12391 7323 56560 84334 63361 68238 58914 91003 83156 16560 48417 48539 12953 67427 95618 43523 54623 72782 66033 14666 42883 44871 52933 8...

result:

ok Answer correct. (1 test case)

Test #13:

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

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:

40770 6329
345 40770 1337 96616 64771 50434 40948 18518 58116 62606 52464 35487 58673 63072 59131 83880 85446 43126 2799 62096 78123 70922 49405 51628 60575 29704 52822 4293 73984 10921 42047 5513 70609 57221 60219 5417 86487 17774 68054 65568 24840 8768 49563 32076 78497 29916 53142 91247 96576 467...

result:

ok Answer correct. (1 test case)

Test #14:

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

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:

1804 9835
232 1804 4752 9330 1353 6059 6715 5494 8455 8601 4635 4409 5548 5900 2599 1697 1445 7373 9341 311 2510 8006 3021 1625 1773 2760 6285 4906 3942 8082 4398 1801 8195 2225 5012 6728 8789 1076 1762 7547 9651 9505 273 2102 9923 6352 4605 8229 6758 7732 3193 9153 630 9003 3590 7086 3758 993 1083 ...

result:

ok Answer correct. (10 test cases)

Test #15:

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

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:

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

result:

ok Answer correct. (1000 test cases)

Test #16:

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

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:

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

result:

ok Answer correct. (500 test cases)

Test #17:

score: 0
Accepted
time: 30ms
memory: 39012kb

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:

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

result:

ok Answer correct. (2197 test cases)

Test #18:

score: 0
Accepted
time: 36ms
memory: 39916kb

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 1
2 3 1 
2 3 1 
2 3 1 
2 3 1 
2 3 1 
2 3 1 
2 3 1 
2 3 1 
2 3 1 
2 3 1 
2 3 1 
2 3 1 
2 3 1 
2 3 1 
2 3 1 
2 3 1 
2 3 1 
2 3 1 
3 3 4 1 
2 3 1 
2 3 1 
2 3 1 
2 3 1 
2 3 1 
2 3 1 
2 3 1 
2 1
2 2 1 
2 2 1 
2 2 1 
2 2 1 
2 2 1 
2 2 1 
2 2 1 
3 2 4 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. (1980 test cases)

Test #19:

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

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:

93067 81584
138 93067 10411 90797 67993 54603 24890 58906 74590 27222 9101 65856 20342 93129 2469 23611 98014 36959 26484 94100 42221 78667 15413 84893 207 9192 18944 7156 62171 45058 51035 30129 47422 17644 93462 6334 59943 52910 10997 73551 40276 24621 31885 19153 43887 9139 28421 14953 25263 4470...

result:

ok Answer correct. (1 test case)

Test #20:

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

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:

40770 6329
345 40770 1337 96616 64771 50434 40948 18518 58116 62606 52464 35487 58673 63072 59131 83880 85446 43126 2799 62096 78123 70922 49405 51628 60575 29704 52822 4293 73984 10921 42047 5513 70609 57221 60219 5417 86487 17774 68054 65568 24840 8768 49563 32076 78497 29916 53142 91247 96576 467...

result:

ok Answer correct. (1 test case)

Test #21:

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

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:

1804 9835
232 1804 4752 9330 1353 6059 6715 5494 8455 8601 4635 4409 5548 5900 2599 1697 1445 7373 9341 311 2510 8006 3021 1625 1773 2760 6285 4906 3942 8082 4398 1801 8195 2225 5012 6728 8789 1076 1762 7547 9651 9505 273 2102 9923 6352 4605 8229 6758 7732 3193 9153 630 9003 3590 7086 3758 993 1083 ...

result:

ok Answer correct. (10 test cases)

Test #22:

score: 0
Accepted
time: 29ms
memory: 39224kb

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:

62 51
2 62 51 
2 62 51 
2 62 51 
2 62 51 
2 62 51 
2 62 51 
2 62 51 
2 62 51 
37 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 730 290 859 511 51 
2 62 51 
2 62 51 
938 708
2 938 708 
2 938 708 
2 938 708 
2 938 708 
53 938...

result:

ok Answer correct. (20 test cases)

Test #23:

score: 0
Accepted
time: 29ms
memory: 40440kb

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

result:

ok Answer correct. (422 test cases)

Test #24:

score: 0
Accepted
time: 28ms
memory: 40244kb

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:

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

result:

ok Answer correct. (46 test cases)

Test #25:

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

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:

677 278
17 677 84 327 200 631 231 426 73 359 111 423 678 548 339 159 541 278 
2 677 278 
256 91
9 256 140 138 631 433 311 868 124 91 
33 256 23 96 370 283 775 736 371 454 402 438 77 783 748 806 350 540 526 651 859 757 470 126 465 340 234 703 300 489 151 502 261 91 
2 256 91 
738 99
12 738 74 202 142...

result:

ok Answer correct. (199 test cases)

Test #26:

score: 0
Accepted
time: 32ms
memory: 42056kb

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:

56 6
12 56 90 20 3 53 32 98 71 43 62 57 6 
6 56 44 89 42 43 6 
12 56 79 14 95 76 25 57 74 58 12 52 6 
4 56 39 78 6 
11 56 20 98 73 37 32 95 30 85 61 6 
9 56 77 47 78 37 14 99 76 6 
4 56 69 36 6 
10 56 5 11 32 34 89 15 20 42 6 
7 56 9 82 95 13 23 6 
12 56 23 13 48 85 9 92 65 73 63 89 6 
13 56 19 88 9...

result:

ok Answer correct. (1 test case)

Test #27:

score: 0
Accepted
time: 44ms
memory: 42860kb

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:

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

result:

ok Answer correct. (1 test case)

Test #28:

score: 0
Accepted
time: 43ms
memory: 43040kb

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:

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

result:

ok Answer correct. (1 test case)

Test #29:

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

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:

85 68
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 68 
2 85 6...

result:

ok Answer correct. (1 test case)

Test #30:

score: 0
Accepted
time: 31ms
memory: 41404kb

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:

36 114
13 36 72 62 131 61 110 34 83 135 40 25 50 114 
17 36 45 42 146 73 58 83 99 143 84 16 106 136 3 11 27 114 
13 36 65 74 1 62 39 137 90 100 127 13 75 114 
7 36 144 142 84 19 130 114 
31 36 68 66 107 53 54 101 18 5 11 85 130 92 84 111 106 35 108 96 17 32 24 99 42 1 138 9 71 23 75 114 
11 36 69 96...

result:

ok Answer correct. (16 test cases)