QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#423563#7855. 不跳棋kkkgjyismine40 1802ms318184kbC++142.9kb2024-05-28 09:56:062024-05-28 09:56:07

Judging History

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

  • [2024-05-28 09:56:07]
  • 评测
  • 测评结果:0
  • 用时:1802ms
  • 内存:318184kb
  • [2024-05-28 09:56:06]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
const int inf=1e9;
ll ct[500050];
int n,tt,tt1,mark[1005000],dis[1005000][21],up[1005000][21],col[1005000][21],dep[1005000];
int mn[1005000];ll Ct[1005000];
vector<int>road[505000],vec[2][1005000];
vector<pii>Road[1005000];
void add(int u,int v,int w){Road[u].pb(mp(v,w)),Road[v].pb(mp(u,w));}
void dfs(int u,int fa){
	int lst=-1;
	for(int v:road[u]){
		if(v==fa)continue;dfs(v,u);
		if(lst==-1){add(u,v,1);continue;}
		int id=++tt;add(lst,id,0),add(id,v,1),lst=id;
	}
}
void dfs1(int u,int fa){
	for(auto v:Road[u]){
		if(v.fi==fa)continue;
		dep[v.fi]=dep[u]+1;
		dfs1(v.fi,u);
	}
}
bool chk(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	return mark[u];
}
int sz[1000005],mx[1000005],rt,rt1;
void find(int u,int fa,int ct1){
	sz[u]=1,mx[u]=0;
	for(auto v:Road[u]){
		if(v.fi==fa||chk(u,v.fi))continue;
		find(v.fi,u,ct1),sz[u]+=sz[v.fi];
	}mx[u]=max(ct1-sz[u],sz[u]);
	if(rt==-1||mx[u]<mx[rt])rt=u,rt1=fa;
}
int Mx[2],ctt[2][1005005],Now[1005005][2];
void init(int u,int fa,int cl,int dp,int id){
	up[u][dp]=id,col[u][dp]=cl,Mx[cl]=max(Mx[cl],dis[u][dp]),sz[u]=1;
	if(u<=n)++ctt[cl][dis[u][dp]];
	for(auto v:Road[u]){
		if(v.fi==fa||chk(u,v.fi))continue;
		dis[v.fi][dp]=dis[u][dp]+v.se;
		init(v.fi,u,cl,dp,id),sz[u]+=sz[v.fi];
	}
}
void solve(int u,int G,int dp){
	if(G<2)return;int p,q,s1,s2;
	rt=-1;find(u,-1,G),p=rt,q=rt1;
	assert(rt1>0);
    if(dep[p]<dep[q])swap(p,q);
    mark[p]=1,++tt1,Mx[0]=Mx[1]=0,dis[p][dp]=dis[q][dp]=0;
    init(p,-1,0,dp,tt1),init(q,-1,1,dp,tt1),s1=sz[p],s2=sz[q];
    mn[tt1]=0,Ct[tt1]=1;
    for(int i=0;i<2;++i){
    	vec[i][tt1].resize(Mx[i]+1);
    	for(int j=0;j<=Mx[i];++j)vec[i][tt1][j]=ctt[i][j],ctt[i][j]=0;
    	Now[tt1][i]=0;
    	while(Now[tt1][i]<=Mx[i]&&!vec[i][tt1][Now[tt1][i]])++Now[tt1][i];
    	if(Now[tt1][i]==Mx[i])mn[tt1]+=inf;
    	else mn[tt1]+=Now[tt1][i],Ct[tt1]*=1ll*vec[i][tt1][Now[tt1][i]];
	}
	if(mn[tt1]<=n)ct[mn[tt1]]+=Ct[tt1];
	solve(p,s1,dp+1),solve(q,s2,dp+1);
}
void upd(int p){
	if(mn[p]>n)return;
	ct[mn[p]]-=Ct[p],mn[p]=1,Ct[p]=1;
	for(int i=0;i<2;++i){
		while(Now[p][i]<vec[i][p].size()&&!vec[i][p][Now[p][i]])++Now[p][i];
		if(Now[p][i]==vec[i][p].size())mn[p]+=inf;
		else mn[p]+=Now[p][i],Ct[p]*=1ll*vec[i][p][Now[p][i]];
	}
	if(mn[p]<=n)ct[mn[p]]+=Ct[p];
}
void del(int p){
	for(int i=0;i<=20;++i){
		if(!up[p][i])continue;
		--vec[col[p][i]][up[p][i]][dis[p][i]],upd(up[p][i]);
	}
}
int Ans,tp;
ll lstans;
int main(){
	scanf("%d%d",&n,&tp),tt=n;
	for(int i=1;i<n;++i){
		int u,v;scanf("%d%d",&u,&v);
		road[u].pb(v),road[v].pb(u);
	}dfs(1,-1),dfs1(1,-1);
	solve(1,tt,0);
	int q=n-2;Ans=1;
	while(q--){
		ll x;scanf("%lld",&x);
		x^=(tp*lstans),del(x);
		while(!ct[Ans])++Ans;
		printf("%d %lld\n",Ans,ct[Ans]),lstans=ct[Ans];
	}
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 11ms
memory: 106296kb

input:

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

output:

1 5
1 8
1 13
1 13
1 14
1 15
1 15
1 17
1 18
1 18
1 20
1 22
1 21
1 21
1 23
1 26
1 25
1 24
1 24
1 24
1 24
1 24
1 24
1 24
1 24
1 23
1 24
1 23
1 23
1 24
1 24
1 23
1 21
1 22
1 22
1 19
1 20
1 20
1 19
1 19
1 17
1 16
1 16
1 16
1 15
1 15
1 15
1 12
1 10
1 11
1 11
1 11
1 11
1 11
1 11
1 10
1 10
1 10
1 10
1 8
1 8...

result:

wrong answer 1st lines differ - expected: '1 97', found: '1 5'

Test #2:

score: 0
Wrong Answer
time: 11ms
memory: 106352kb

input:

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

output:

1 4
1 7
1 10
1 12
1 13
1 14
1 14
1 13
1 14
1 16
1 14
1 16
1 12
1 11
1 11
1 12
1 12
1 9
1 9
1 11
1 10
1 11
1 12
1 13
1 13
1 13
1 13
1 13
1 13
1 12
1 12
1 11
1 11
1 11
1 12
1 12
1 10
1 7
1 7
1 7
1 7
1 7
1 7
1 7
1 7
1 7
1 7
1 7
1 7
1 6
1 6
1 6
1 6
1 6
1 6
1 6
1 6
1 5
1 5
1 5
1 5
1 4
1 3
1 3
1 3
1 3
1 2...

result:

wrong answer 1st lines differ - expected: '1 94', found: '1 4'

Test #3:

score: 0
Wrong Answer
time: 11ms
memory: 106352kb

input:

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

output:

1 4
1 7
1 6
1 10
1 12
1 12
1 12
1 14
1 13
1 15
1 14
1 14
1 15
1 14
1 14
1 15
1 16
1 16
1 15
1 15
1 15
1 15
1 15
1 15
1 15
1 15
1 15
1 15
1 14
1 14
1 13
1 11
1 12
1 12
1 11
1 11
1 9
1 7
1 7
1 6
1 6
1 6
1 4
1 4
1 4
1 4
1 4
1 4
1 4
1 3
1 3
1 3
1 3
1 3
1 3
1 3
1 3
1 3
1 3
1 3
1 3
1 3
1 2
1 2
1 2
1 2
1 2...

result:

wrong answer 1st lines differ - expected: '1 95', found: '1 4'

Test #4:

score: 0
Wrong Answer
time: 16ms
memory: 106420kb

input:

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

output:

1 8
1 15
1 21
1 26
1 32
1 38
1 40
1 40
1 48
1 47
1 50
1 53
1 53
1 57
1 57
1 56
1 54
1 56
1 61
1 61
1 66
1 69
1 75
1 77
1 81
1 83
1 84
1 87
1 90
1 97
1 97
1 96
1 99
1 103
1 103
1 107
1 108
1 111
1 113
1 116
1 117
1 117
1 120
1 120
1 121
1 123
1 124
1 127
1 127
1 126
1 129
1 128
1 131
1 132
1 131
1 13...

result:

wrong answer 1st lines differ - expected: '1 998', found: '1 8'

Test #5:

score: 0
Wrong Answer
time: 8ms
memory: 106344kb

input:

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

output:

1 10
1 18
1 24
1 32
1 35
1 35
1 37
1 38
1 41
1 46
1 48
1 52
1 57
1 64
1 68
1 72
1 74
1 77
1 82
1 83
1 83
1 85
1 85
1 89
1 91
1 91
1 94
1 100
1 104
1 106
1 101
1 107
1 110
1 112
1 113
1 115
1 114
1 118
1 118
1 121
1 122
1 122
1 126
1 125
1 127
1 127
1 128
1 130
1 131
1 132
1 132
1 135
1 137
1 136
1 1...

result:

wrong answer 1st lines differ - expected: '1 997', found: '1 10'

Test #6:

score: 0
Wrong Answer
time: 15ms
memory: 106520kb

input:

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

output:

1 8
1 15
1 18
1 18
1 24
1 31
1 36
1 40
1 46
1 50
1 55
1 61
1 64
1 65
1 67
1 70
1 72
1 77
1 78
1 83
1 85
1 90
1 94
1 96
1 100
1 103
1 106
1 106
1 106
1 108
1 111
1 116
1 118
1 122
1 124
1 126
1 128
1 129
1 129
1 131
1 133
1 137
1 140
1 140
1 141
1 142
1 145
1 144
1 144
1 144
1 147
1 149
1 150
1 148
1...

result:

wrong answer 1st lines differ - expected: '1 997', found: '1 8'

Test #7:

score: 0
Wrong Answer
time: 600ms
memory: 195432kb

input:

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

output:

1 18
1 33
1 48
1 59
1 67
1 80
1 93
1 103
1 113
1 123
1 132
1 143
1 156
1 170
1 183
1 194
1 202
1 214
1 218
1 227
1 240
1 250
1 261
1 275
1 286
1 293
1 303
1 308
1 317
1 328
1 343
1 351
1 363
1 374
1 382
1 387
1 396
1 409
1 418
1 425
1 432
1 445
1 453
1 461
1 468
1 477
1 483
1 490
1 498
1 505
1 515
1...

result:

wrong answer 1st lines differ - expected: '1 199998', found: '1 18'

Test #8:

score: 0
Wrong Answer
time: 586ms
memory: 194840kb

input:

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

output:

1 14
1 31
1 44
1 55
1 66
1 82
1 97
1 107
1 118
1 127
1 139
1 152
1 161
1 171
1 182
1 196
1 209
1 212
1 220
1 229
1 240
1 250
1 261
1 272
1 286
1 293
1 304
1 315
1 326
1 335
1 349
1 357
1 369
1 377
1 386
1 396
1 407
1 418
1 426
1 433
1 442
1 450
1 462
1 472
1 479
1 488
1 499
1 506
1 517
1 529
1 538
1...

result:

wrong answer 1st lines differ - expected: '1 199997', found: '1 14'

Test #9:

score: 0
Wrong Answer
time: 603ms
memory: 193476kb

input:

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

output:

1 16
1 32
1 48
1 61
1 77
1 89
1 97
1 109
1 120
1 127
1 138
1 150
1 159
1 171
1 182
1 193
1 205
1 218
1 225
1 234
1 243
1 255
1 261
1 272
1 285
1 296
1 305
1 311
1 320
1 330
1 341
1 349
1 359
1 366
1 376
1 388
1 396
1 408
1 420
1 428
1 438
1 446
1 454
1 462
1 473
1 483
1 494
1 504
1 514
1 526
1 532
1...

result:

wrong answer 1st lines differ - expected: '1 199996', found: '1 16'

Test #10:

score: 0
Wrong Answer
time: 412ms
memory: 217248kb

input:

200000 0
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:

1 15
1 27
1 41
1 54
1 67
1 79
1 90
1 98
1 109
1 120
1 133
1 144
1 156
1 165
1 176
1 186
1 196
1 205
1 212
1 223
1 232
1 241
1 252
1 260
1 271
1 281
1 292
1 304
1 313
1 323
1 334
1 344
1 354
1 359
1 367
1 374
1 382
1 390
1 397
1 408
1 418
1 425
1 436
1 442
1 452
1 460
1 467
1 478
1 485
1 493
1 502
1 ...

result:

wrong answer 1st lines differ - expected: '1 199997', found: '1 15'

Test #11:

score: 0
Wrong Answer
time: 432ms
memory: 197332kb

input:

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

output:

1 15
1 27
1 41
1 52
1 62
1 71
1 82
1 91
1 106
1 117
1 129
1 139
1 152
1 166
1 176
1 187
1 199
1 211
1 223
1 232
1 239
1 249
1 257
1 266
1 275
1 286
1 296
1 306
1 315
1 326
1 336
1 348
1 356
1 368
1 379
1 388
1 399
1 407
1 409
1 420
1 429
1 437
1 448
1 458
1 466
1 475
1 483
1 492
1 501
1 505
1 515
1 ...

result:

wrong answer 1st lines differ - expected: '1 199997', found: '1 15'

Test #12:

score: 0
Wrong Answer
time: 450ms
memory: 199288kb

input:

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

output:

1 16
1 31
1 43
1 53
1 65
1 77
1 90
1 103
1 117
1 128
1 140
1 149
1 155
1 163
1 176
1 184
1 190
1 202
1 208
1 219
1 230
1 242
1 254
1 262
1 271
1 282
1 283
1 295
1 306
1 315
1 324
1 330
1 338
1 350
1 359
1 368
1 378
1 387
1 394
1 403
1 412
1 423
1 431
1 439
1 449
1 457
1 465
1 470
1 478
1 483
1 489
1...

result:

wrong answer 1st lines differ - expected: '1 199996', found: '1 16'

Test #13:

score: 0
Wrong Answer
time: 390ms
memory: 213816kb

input:

200000 1
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:

1 16
1 29
1 29
1 29
1 40
1 40
1 40
1 51
1 64
1 78
1 90
1 101
1 101
1 111
1 121
1 121
1 129
1 138
1 150
1 150
1 156
1 166
1 176
1 187
1 197
1 197
1 205
1 218
1 224
1 233
1 243
1 252
1 264
1 271
1 281
1 281
1 290
1 301
1 301
1 301
1 310
1 310
1 310
1 319
1 319
1 319
1 319
1 319
1 327
1 327
1 336
1 336...

result:

wrong answer 1st lines differ - expected: '1 199997', found: '1 16'

Test #14:

score: 0
Wrong Answer
time: 406ms
memory: 220988kb

input:

200000 1
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:

1 15
1 29
1 42
1 48
1 48
1 58
1 58
1 69
1 77
1 77
1 89
1 89
1 89
1 89
1 89
1 89
1 102
1 112
1 112
1 124
1 131
1 144
1 144
1 156
1 156
1 167
1 167
1 167
1 178
1 188
1 188
1 196
1 207
1 213
1 221
1 230
1 230
1 230
1 240
1 240
1 249
1 258
1 268
1 277
1 287
1 287
1 295
1 305
1 316
1 316
1 326
1 332
1 33...

result:

wrong answer 1st lines differ - expected: '1 199997', found: '1 15'

Test #15:

score: 0
Wrong Answer
time: 253ms
memory: 222784kb

input:

200000 1
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:

1 16
1 30
1 32
1 33
1 33
1 33
1 33
1 37
1 37
1 37
1 37
1 36
1 35
1 35
1 36
1 35
1 35
1 35
1 35
1 35
1 35
1 35
1 35
1 34
1 33
1 33
1 33
1 35
1 35
1 35
1 35
1 35
1 40
1 43
1 43
1 43
1 43
1 42
1 42
1 43
1 43
1 43
1 43
1 43
1 43
1 43
1 43
1 45
1 44
1 44
1 44
1 44
1 44
1 44
1 44
1 43
1 43
1 43
1 43
1 43
...

result:

wrong answer 1st lines differ - expected: '1 199997', found: '1 16'

Test #16:

score: 0
Wrong Answer
time: 385ms
memory: 213960kb

input:

200000 1
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:

1 16
1 28
1 42
1 54
1 67
1 72
1 81
1 95
1 106
1 115
1 125
1 137
1 149
1 149
1 160
1 160
1 172
1 183
1 191
1 203
1 214
1 223
1 232
1 242
1 242
1 242
1 252
1 262
1 270
1 270
1 270
1 270
1 277
1 286
1 286
1 286
1 296
1 304
1 314
1 321
1 321
1 321
1 329
1 329
1 336
1 341
1 349
1 358
1 365
1 365
1 372
1 ...

result:

wrong answer 1st lines differ - expected: '1 199997', found: '1 16'

Test #17:

score: 0
Wrong Answer
time: 597ms
memory: 190848kb

input:

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

output:

1 15
1 28
1 42
1 42
1 42
1 55
1 67
1 81
1 81
1 93
1 106
1 106
1 118
1 118
1 129
1 129
1 145
1 145
1 145
1 145
1 156
1 165
1 174
1 186
1 196
1 206
1 213
1 213
1 229
1 229
1 229
1 240
1 251
1 261
1 265
1 277
1 288
1 288
1 299
1 299
1 312
1 312
1 328
1 338
1 338
1 338
1 338
1 338
1 349
1 349
1 355
1 36...

result:

wrong answer 1st lines differ - expected: '1 199998', found: '1 15'

Test #18:

score: 0
Wrong Answer
time: 581ms
memory: 195244kb

input:

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

output:

1 15
1 15
1 28
1 42
1 58
1 58
1 73
1 82
1 82
1 95
1 95
1 108
1 119
1 119
1 131
1 131
1 131
1 143
1 156
1 168
1 168
1 168
1 179
1 193
1 205
1 205
1 205
1 217
1 227
1 240
1 253
1 266
1 266
1 266
1 266
1 276
1 289
1 298
1 298
1 302
1 302
1 302
1 309
1 321
1 330
1 339
1 351
1 351
1 351
1 351
1 360
1 369...

result:

wrong answer 1st lines differ - expected: '1 199997', found: '1 15'

Test #19:

score: 0
Wrong Answer
time: 388ms
memory: 197468kb

input:

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

output:

1 15
1 28
1 28
1 34
1 34
1 45
1 45
1 45
1 45
1 45
1 55
1 67
1 81
1 81
1 94
1 94
1 94
1 105
1 105
1 116
1 126
1 126
1 126
1 136
1 136
1 149
1 154
1 154
1 154
1 154
1 166
1 176
1 189
1 197
1 197
1 207
1 217
1 217
1 228
1 237
1 237
1 250
1 260
1 272
1 280
1 287
1 295
1 295
1 304
1 307
1 316
1 326
1 335...

result:

wrong answer 1st lines differ - expected: '1 199996', found: '1 15'

Test #20:

score: 0
Wrong Answer
time: 403ms
memory: 201476kb

input:

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

output:

1 15
1 30
1 38
1 50
1 63
1 76
1 89
1 97
1 97
1 97
1 111
1 123
1 134
1 134
1 134
1 143
1 157
1 166
1 177
1 177
1 187
1 197
1 197
1 197
1 207
1 215
1 215
1 227
1 227
1 236
1 245
1 245
1 252
1 252
1 263
1 263
1 272
1 272
1 272
1 272
1 272
1 281
1 287
1 298
1 298
1 306
1 306
1 306
1 316
1 325
1 335
1 34...

result:

wrong answer 1st lines differ - expected: '1 199997', found: '1 15'

Test #21:

score: 0
Time Limit Exceeded

input:

500000 1
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 61...

output:


result:


Test #22:

score: 0
Wrong Answer
time: 1784ms
memory: 315836kb

input:

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

output:

1 17
1 31
1 49
1 61
1 77
1 91
1 103
1 117
1 127
1 140
1 151
1 162
1 178
1 185
1 199
1 207
1 217
1 227
1 239
1 250
1 265
1 271
1 285
1 285
1 300
1 311
1 321
1 332
1 346
1 356
1 367
1 379
1 391
1 403
1 416
1 429
1 439
1 450
1 455
1 471
1 479
1 487
1 497
1 508
1 517
1 517
1 532
1 538
1 550
1 556
1 567
...

result:

wrong answer 1st lines differ - expected: '1 499998', found: '1 17'

Test #23:

score: 0
Wrong Answer
time: 1802ms
memory: 316144kb

input:

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

output:

1 14
1 34
1 46
1 61
1 74
1 91
1 101
1 119
1 130
1 141
1 156
1 166
1 175
1 186
1 200
1 210
1 225
1 231
1 243
1 252
1 268
1 279
1 293
1 307
1 318
1 329
1 341
1 354
1 361
1 374
1 374
1 386
1 393
1 399
1 406
1 415
1 425
1 438
1 438
1 450
1 457
1 471
1 479
1 490
1 496
1 509
1 520
1 531
1 543
1 551
1 562
...

result:

wrong answer 1st lines differ - expected: '1 499998', found: '1 14'

Test #24:

score: 0
Wrong Answer
time: 1768ms
memory: 316132kb

input:

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

output:

1 19
1 27
1 45
1 59
1 67
1 81
1 96
1 114
1 126
1 140
1 154
1 167
1 182
1 196
1 209
1 217
1 227
1 243
1 253
1 265
1 276
1 289
1 302
1 304
1 316
1 322
1 329
1 341
1 355
1 366
1 379
1 389
1 401
1 412
1 424
1 435
1 435
1 444
1 455
1 467
1 467
1 481
1 491
1 504
1 517
1 526
1 536
1 548
1 559
1 573
1 584
1...

result:

wrong answer 1st lines differ - expected: '1 499998', found: '1 19'

Test #25:

score: 0
Wrong Answer
time: 1734ms
memory: 318184kb

input:

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

output:

1 12
1 28
1 46
1 58
1 72
1 83
1 100
1 111
1 124
1 138
1 152
1 164
1 174
1 182
1 192
1 204
1 214
1 225
1 240
1 253
1 262
1 269
1 269
1 275
1 290
1 304
1 317
1 327
1 332
1 344
1 355
1 366
1 378
1 389
1 400
1 409
1 409
1 420
1 429
1 443
1 443
1 454
1 466
1 473
1 480
1 489
1 501
1 510
1 520
1 531
1 543
...

result:

wrong answer 1st lines differ - expected: '1 499992', found: '1 12'