QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#227719#7610. Bus Lines275307894aTL 4997ms178368kbC++144.0kb2023-10-27 21:59:442023-10-27 21:59:45

Judging History

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

  • [2023-10-27 21:59:45]
  • 评测
  • 测评结果:TL
  • 用时:4997ms
  • 内存:178368kb
  • [2023-10-27 21:59:44]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=2e5+5,M=N*8+5,K=(1<<25)+5,mod=1e9+7,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
int n,x,y;
vector<int> S[N];
int fa[N],d[N],Sn[N],Si[N],Tp[N],Bg[N],Bh,En[N],Df[N];
void dfs1(int x,int La){
	fa[x]=La;d[x]=d[La]+1;Si[x]=1;
	for(int i:S[x]) if(i^La) dfs1(i,x),Si[x]+=Si[i],Si[Sn[x]]<Si[i]&&(Sn[x]=i);
}
void dfs2(int x,int La){
	Df[Bg[x]=++Bh]=x;Tp[x]=La;if(Sn[x]) dfs2(Sn[x],La);
	for(int i:S[x]) if(i^fa[x]&&i^Sn[x]) dfs2(i,i);En[x]=Bh;
}
vector<pair<int,int> > E;
int LCA(int x,int y){
	E.clear();while(Tp[x]^Tp[y]) {
		if(d[Tp[x]]<d[Tp[y]]) swap(x,y);
		E.emplace_back(Bg[Tp[x]],Bg[x]);x=fa[Tp[x]];
	}
	if(d[x]>d[y]) swap(x,y);E.emplace_back(Bg[x],Bg[y]);return x;
} 
ll f[N],g[N],w[N],ans[N];int up[N];
struct node{int x,y,ti;};
vector<node> Q[N];vector<pair<int,int> > D[N];
namespace Tree{
	#define ls v<<1
	#define rs v<<1|1
	int lim;void BD(){lim=1<<__lg(n+5)+1;}
	int g[M];ll Sum[M],f[M];
	void Up(int v){f[v]=(g[v]?Sum[v]:f[ls]+f[rs]);}
	void PF(int v,int w){g[v]+=w;Up(v);}
	void Add(int x,int y,int w,int l=0,int r=lim-1,int v=1){
		x--;y++;x+=lim;y+=lim;
		while(x^y^1) {
			if(!(x&1)) PF(x^1,w);if(y&1) PF(y^1,w);
			x>>=1;y>>=1;Up(x);Up(y);
		}
		while(x^1) x>>=1,Up(x);
		// if(x<=l&&r<=y) return PF(v,w);int m=l+r>>1;
		// x<=m&&(Add(x,y,w,l,m,ls),0);y>m&&(Add(x,y,w,m+1,r,rs),0);Up(v);
	}
	void modify(int x,ll w,int l=0,int r=lim-1,int v=1){
		Sum[v]+=w;if(l==r) return Up(v);int m=l+r>>1;
		x<=m?modify(x,w,l,m,ls):modify(x,w,m+1,r,rs);Up(v);
	}
	ll qry(int x,int y,int op=0,int l=0,int r=lim-1,int v=1){
		if(x>y) return 0;op|=g[v];
		if(x<=l&&r<=y) return op?Sum[v]:f[v];int m=l+r>>1;
		return (x<=m?qry(x,y,op,l,m,ls):0)+(y>m?qry(x,y,op|g[v],m+1,r,rs):0);
	}
}
int YAI;
int MIN(int x,int y){return d[x]<d[y]?x:y;}
void ins(int x,int La,int w,int ti){
	for(auto i:Q[x]) if(i.ti<ti) Tree::Add(i.x,i.y,w),YAI++;
	for(int i:S[x]) if(i^La) ins(i,x,w,ti);
}
void dfs3(int x,int La){
	for(int i:S[x]) if(i^La) dfs3(i,x);
	for(auto i:Q[x]) Tree::Add(i.x,i.y,1);
	for(auto i:D[x]) Tree::Add(i.fi,i.se,-2);
	f[x]=En[x]-Bg[x]+1;
	f[x]+=Tree::qry(Bg[x]+1,En[x]);
	for(int i:S[x]) if(i^La) f[x]+=f[i];
	w[x]=-f[x];for(int i:S[x]) if(i^La) w[x]+=f[i];
	Tree::modify(Bg[x],w[x]);
	for(int i:S[x]) if(i^La) up[x]=MIN(up[x],up[i]);
}
void dfs4(int x,int La){
	for(int i:S[x]) if(i^La&&i^Sn[x]) dfs4(i,x),ins(i,x,-1,d[i]);
	if(Sn[x]) dfs4(Sn[x],x);
	for(int i:S[x]) if(i^La&&i^Sn[x]) ins(i,x,1,d[i]);
	for(auto i:Q[x]) Tree::Add(i.x,i.y,1);
	for(auto i:D[x]) Tree::Add(i.fi,i.se,-2);
	g[x]=n-(En[x]-Bg[x]+1);
	g[x]+=Tree::f[1]-Tree::qry(Bg[x],En[x]);
	// g[x]+=g[up[x]]+f[up[x]];
	g[x]-=f[x];
	// cerr<<x<<' '<<g[x]<<'\n';
}
void Make(int x,int La){g[x]+=g[up[x]]+f[up[x]];/*cerr<<g[x]<<'\n';*/if(!La) g[x]=0;for(int i:S[x]) if(i^La) Make(i,x);}
void Solve(){
	int i,j;scanf("%d",&n);
	for(i=1;i<n;i++) {
		int x,y;scanf("%d%d",&x,&y);
		S[x].eb(y);S[y].eb(x);
	}
	Tree::BD();
	int Rt=1;
	dfs1(Rt,0);dfs2(Rt,Rt);
	int m;scanf("%d",&m);
	iota(up+1,up+n+1,1);
	while(m--){
		int x,y;scanf("%d%d",&x,&y);
		int Ls=LCA(x,y);up[x]=MIN(up[x],Ls);up[y]=MIN(up[y],Ls);
		// for(auto i:E) for(int j=i.fi;j<=i.se;j++) A[x][j]++,A[y][j]++,A[Ls][j]-=2;
		for(auto i:E) Q[x].eb((node){i.fi,i.se,d[Ls]}),Q[y].eb((node){i.fi,i.se,d[Ls]}),D[Ls].eb(i);
	}
	dfs3(Rt,0);dfs4(Rt,0);Make(Rt,0);
	for(i=1;i<=n;i++){
		ans[i]=g[i];for(int j:S[i]) if(j^fa[i]) ans[i]+=f[j];
		printf("%lld ",ans[i]);
	}
	cerr<<YAI<<'\n';
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 32584kb

input:

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

output:

6 9 9 10 7 7 

result:

ok single line: '6 9 9 10 7 7 '

Test #2:

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

input:

2
1 2
1
1 2

output:

1 1 

result:

ok single line: '1 1 '

Test #3:

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

input:

16384
9137 490
3442 7239
1621 6904
13769 10250
14672 12572
14906 9437
6163 12339
15244 12016
3022 8670
3211 9106
11966 14817
15798 15876
6423 7394
894 7695
13877 1983
16342 15158
13574 15932
15125 10722
6989 15683
10335 8801
12301 4246
6166 3893
9347 12073
7897 12195
6510 3101
4526 15385
7017 7001
4...

output:

34355 34048 34070 34152 33992 33977 34077 42219 34103 33976 34065 34170 34072 34061 34069 34177 34068 34129 33872 50478 34059 33921 34153 34049 34034 33820 34132 34116 34361 33728 50043 34138 33855 33873 34309 34319 34068 50753 34135 34256 34159 34034 34056 34361 34171 34316 34058 34125 34019 34182 ...

result:

ok single line: '34355 34048 34070 34152 33992 ... 34333 33814 33294 34266 34337 '

Test #4:

score: 0
Accepted
time: 761ms
memory: 64864kb

input:

65536
44501 44259
59772 51161
51582 2027
2699 8610
5021 57211
60597 10270
29222 11423
38503 3833
52021 47503
47160 15296
61201 13465
20807 17239
7705 20234
32708 25663
7800 42265
29410 44963
32173 38920
49438 61282
25922 4342
40171 9819
12256 3995
41600 39383
57051 60932
44275 8351
8356 8295
3557 64...

output:

140178 136111 137025 136494 136304 137262 136598 135563 136530 135406 199677 137437 140282 136109 140127 136827 137235 136000 140738 139961 140081 142677 136544 201610 136181 136393 137013 137354 136855 135440 127050 136828 136781 137439 136518 185910 137170 136902 140686 136703 136847 137483 136337...

result:

ok single line: '140178 136111 137025 136494 13...63 136343 136858 137469 137325 '

Test #5:

score: 0
Accepted
time: 2355ms
memory: 121568kb

input:

131071
28270 44685
69228 113487
10873 80967
30958 109340
53006 103488
49569 111875
65021 32861
83043 36671
73613 119374
22104 91373
31527 27737
19718 27803
90762 87148
4096 41649
79425 111516
111950 123500
94580 61416
30879 18640
71251 76344
61698 28557
104875 59268
130832 61334
110927 109064
114115...

output:

273557 262588 264936 265663 265875 266353 265834 265712 376149 272370 267699 267626 267023 265515 266009 265333 278296 265843 265760 268149 267395 265340 271825 358266 268835 264845 266112 265586 265886 266374 265323 265391 266080 265499 278600 267120 265190 266164 266010 265240 265690 265370 264312...

result:

ok single line: '273557 262588 264936 265663 26...42 266079 265822 265939 266211 '

Test #6:

score: 0
Accepted
time: 610ms
memory: 66164kb

input:

131071
4458 33223
28971 26710
73930 35887
19953 56582
19448 128895
117093 55994
68752 16511
37373 128666
1236 73891
64724 74049
67901 130974
130547 112357
99689 77958
76785 17021
37348 91813
67628 67488
96598 83555
17348 74226
98935 43076
75325 83600
59427 80746
74874 122816
71615 76503
112584 12953...

output:

131070 131070 131070 131070 131070 131070 131071 131071 131071 131071 131070 131071 131070 131070 131071 131071 131070 131071 131071 131070 131070 131070 131070 131070 131071 131070 131070 131070 131070 131070 131070 131071 131070 131071 131070 131070 131070 131070 131070 131071 131070 131070 131071...

result:

ok single line: '131070 131070 131070 131070 13...70 131071 131070 131070 131071 '

Test #7:

score: 0
Accepted
time: 2519ms
memory: 119452kb

input:

131072
20415 30901
24973 116658
50309 77228
14138 108175
122283 105254
80524 41943
16756 109108
113505 71325
9649 106367
125747 68730
27704 18831
12993 123364
57489 129424
96113 82877
44188 4472
5704 86388
73653 70774
41742 33080
6701 59595
80297 22453
59925 75977
88478 91057
97666 26155
30080 55382...

output:

267346 265658 267019 267148 266495 270630 265327 266124 266100 265926 265909 266766 265785 266284 265064 266584 266146 266937 271485 265805 265480 266087 267189 264771 266288 266965 270451 265977 265706 265268 265845 267259 265723 266249 266047 266159 270563 266086 265976 265845 265431 265535 265930...

result:

ok single line: '267346 265658 267019 267148 26...80 270694 266015 266101 265704 '

Test #8:

score: 0
Accepted
time: 623ms
memory: 65116kb

input:

131072
48550 41416
47329 96006
106074 122239
948 75631
112525 117270
3358 7210
30446 101867
16965 11336
78371 58088
21081 102637
76025 92177
102359 2073
11618 50130
79150 120277
30847 51845
72881 58212
125170 71210
1909 8660
120236 81594
127702 49237
32584 53272
5049 20955
31844 125464
119524 100808...

output:

131071 131072 131078 131071 131071 131072 131072 131072 131074 131071 131071 131071 131072 131071 131071 131072 131072 131072 131071 131115 131078 131072 131074 131071 131072 131074 131071 131071 131072 131072 131074 131074 131072 131072 131074 131072 131078 131072 131077 131074 131071 131072 131072...

result:

ok single line: '131071 131072 131078 131071 13...71 131074 131072 131072 131072 '

Test #9:

score: 0
Accepted
time: 2352ms
memory: 118420kb

input:

131073
113890 124822
124669 105393
128510 64051
106729 33462
46677 33217
73570 96913
47532 130531
8593 45487
31793 58221
49510 82943
60351 62272
42636 37378
105049 94689
124230 45945
13194 123517
107928 62129
7572 15657
84304 122943
19818 59980
104221 18821
66457 91449
5072 101241
61822 5975
74471 6...

output:

266326 266281 266163 265817 265563 266929 265938 266796 265751 265513 266249 269598 266832 267310 265225 266439 266351 265499 397338 269917 266647 266193 266663 266655 269976 266497 326968 266761 266261 266672 265613 266103 265821 265496 265891 266411 265820 266598 266583 266154 265794 265587 266472...

result:

ok single line: '266326 266281 266163 265817 26...69 266180 266343 268563 266527 '

Test #10:

score: 0
Accepted
time: 691ms
memory: 62292kb

input:

131073
30694 94981
78010 61921
83010 76565
7176 94673
24081 63906
107002 35122
72499 90887
98339 109807
48362 125168
5335 63101
127350 85675
13421 77562
2375 93853
10090 23323
91852 109502
21899 90367
56580 125803
108402 88380
30465 25789
73326 29902
60781 28952
113429 111420
15039 5166
48046 85049
...

output:

131072 131072 131073 131072 131072 131072 131072 131072 131072 131072 131072 131205 131072 131072 131072 131083 131073 131072 131083 131073 131072 131072 131072 131072 131073 131073 131072 131072 131072 131072 131072 131072 131072 131072 131072 131083 131073 131073 131072 131194 131205 131072 131072...

result:

ok single line: '131072 131072 131073 131072 13...72 131072 131072 131072 131072 '

Test #11:

score: 0
Accepted
time: 917ms
memory: 74196kb

input:

200000
303 187602
17443 90857
141584 9689
98281 37564
34044 95754
47052 855
176062 121958
162738 96296
89316 164507
150496 42874
12673 1114
24877 131213
196802 28543
78558 84878
102156 146853
143846 158517
167159 69770
16743 9610
169056 115672
127506 149401
4110 24877
150803 72957
71484 24773
50738 ...

output:

200000 200000 200001 200009 200000 200000 200000 200004 200000 200001 200009 200040 200000 200000 200371 200001 200001 200000 200005 200000 200103 200000 200005 200001 200002 200000 200004 200000 200004 200002 200001 200004 200000 200004 200103 200000 200001 200001 200009 200004 200000 200000 200009...

result:

ok single line: '200000 200000 200001 200009 20...00 200000 200000 200001 200001 '

Test #12:

score: 0
Accepted
time: 907ms
memory: 78428kb

input:

200000
91261 108952
134236 7809
30750 140934
69514 100626
174539 64746
143756 139270
75999 163614
73309 112948
110641 128653
77295 196144
112549 15212
29529 58568
34742 48981
160465 37279
60772 47631
116260 164168
140007 138837
152400 41600
46137 103771
122809 991
98335 53547
71446 60454
182926 9505...

output:

259717 224832 623118 233065 221904 225116 248347 347328 229609 227413 369557 318840 231176 228808 255754 223173 224794 339975 239690 230310 252630 225403 411260 227236 240962 241886 231002 333731 242413 226478 294844 238042 224724 260233 244253 330794 247474 231750 283982 269581 221874 223906 258662...

result:

ok single line: '259717 224832 623118 233065 22...21 228869 224599 227932 221883 '

Test #13:

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

input:

3
3 2
1 3
1
1 2

output:

2 2 2 

result:

ok single line: '2 2 2 '

Test #14:

score: 0
Accepted
time: 1152ms
memory: 77720kb

input:

200000
139347 147721
117297 105382
77192 197023
48135 123968
192172 102714
134778 129103
89903 62952
133541 38908
157094 5072
98697 154745
126329 161358
10578 175752
174214 105555
128475 68598
37906 187226
161543 11243
153891 97890
8751 74708
1967 76185
67263 189209
68782 199622
163887 141633
176004...

output:

322099 242574 317560 692202 290760 228294 365767 338369 353452 316822 250525 392353 334147 230213 228522 235083 402948 230055 390730 404058 356419 260604 408966 344671 228306 285866 230909 242013 251050 312234 247399 300014 275307 396635 301629 245071 324672 317767 338521 318599 251342 394339 233005...

result:

ok single line: '322099 242574 317560 692202 29...72 316661 233236 238848 229144 '

Test #15:

score: 0
Accepted
time: 1256ms
memory: 81800kb

input:

200000
48091 145114
125125 28630
12239 122518
46999 28599
9536 79090
173383 59215
130797 80267
19356 192091
70170 63308
51543 84599
75128 23622
67565 61168
59080 1306
169051 40849
189030 31373
186212 42004
87480 32135
81468 163743
112945 69079
83894 23714
71122 15016
66755 85285
115054 110310
3811 4...

output:

352484 361697 353433 343102 240568 351386 298596 364831 245058 343138 260208 258681 345310 370366 432737 233034 361503 405572 231637 345073 347968 358736 232149 353892 398610 251240 431731 345221 343820 346239 347060 263522 231954 393526 360199 379830 373877 236327 353553 603138 426721 241772 231332...

result:

ok single line: '352484 361697 353433 343102 24...94 353707 382734 557096 397978 '

Test #16:

score: 0
Accepted
time: 1410ms
memory: 83484kb

input:

200000
100856 98512
7263 55794
118589 8600
181408 78844
136926 96808
184915 65090
34153 123222
81629 114888
41173 81343
115395 158775
74974 23534
3836 68657
105617 97663
76598 41608
28787 13900
100912 96168
68712 136985
80113 56372
112283 126282
119777 137629
165008 120438
53426 26030
78094 83600
18...

output:

385605 380500 397966 236324 577262 360773 233242 371405 362611 369437 365600 386222 381693 250148 585672 376752 366566 253349 377273 388253 269521 263111 427010 369947 392348 389317 423904 233334 252314 359670 387478 359580 233140 434587 321068 233635 234253 365444 235007 599141 373618 362626 360872...

result:

ok single line: '385605 380500 397966 236324 57...45 241541 407294 372787 439030 '

Test #17:

score: 0
Accepted
time: 1808ms
memory: 91100kb

input:

200000
180714 64749
50294 63588
118425 45210
19449 119242
106397 111631
165556 58767
54399 99326
53093 31192
63207 75350
36668 124604
80509 124402
69687 129300
190278 28893
50196 134511
46249 169905
58139 53110
87694 22713
75518 99566
179781 17413
110365 34464
27454 193678
130171 47991
174341 58040
...

output:

409591 396787 395821 239526 599035 470672 428144 397055 392027 394551 439143 394596 388894 404545 405346 348418 392047 593706 389817 326075 394143 396508 393233 425007 399946 397646 399058 595850 413576 389700 412903 417007 392550 401326 462627 392588 275297 400751 395385 395593 398254 244287 415091...

result:

ok single line: '409591 396787 395821 239526 59...05 410665 400756 392347 468683 '

Test #18:

score: 0
Accepted
time: 2147ms
memory: 98288kb

input:

200000
30933 92193
77862 62042
158213 175855
16780 145844
1108 114460
160478 9352
82719 112145
142088 62191
15793 183238
129644 169759
70407 173026
113244 57481
56239 24998
45541 79142
119610 110586
99594 22588
198974 169804
99392 125472
63750 161647
119893 161584
25389 132271
48396 138568
63641 385...

output:

603675 406633 422392 407572 409097 406433 406205 407058 420803 408723 464911 425536 410465 481876 407605 576569 607865 431005 412229 419713 410499 412896 408749 606713 403730 427776 408406 407828 606627 417814 407449 407308 404474 470975 410304 412734 413266 406163 408984 403576 406249 405420 406787...

result:

ok single line: '603675 406633 422392 407572 40...37 412018 406965 408388 609396 '

Test #19:

score: 0
Accepted
time: 2646ms
memory: 109432kb

input:

200000
53058 81131
171867 48542
51107 57582
48378 14960
8723 5010
161623 59486
63739 114343
146033 97144
38395 143404
106830 120862
166654 142711
17747 75675
115326 57950
141271 125647
172839 194710
87377 142587
179489 111106
83353 29003
25273 100804
126366 129214
377 22864
136214 154742
26790 69245...

output:

410194 414485 812212 409671 417799 607529 444323 439505 398218 413075 406897 417525 409744 418032 416266 417491 409650 420260 411460 411034 412949 416088 409367 613828 410798 608605 411940 403730 303206 404280 403397 612430 415487 395351 408532 419160 418430 410453 416946 618525 408493 411347 423058...

result:

ok single line: '410194 414485 812212 409671 41...85 413258 416216 407728 410996 '

Test #20:

score: 0
Accepted
time: 2973ms
memory: 118728kb

input:

200000
59158 51892
164326 130454
199875 147324
154595 198150
175219 8364
108094 125630
131696 93091
63992 91024
129143 10985
79964 129833
193970 137750
130697 130080
103615 11370
83315 137120
141683 168619
130441 168268
163828 3410
76009 110247
59575 155246
124663 70547
152379 94187
114650 89902
282...

output:

418785 413603 418648 419139 412502 406320 410977 412124 407379 402640 419358 416320 407945 412692 414142 413490 413278 416746 410595 418751 415083 413390 420604 412779 418777 613129 408587 406350 413893 413360 413188 418726 401511 408363 419082 414357 526212 413422 601652 413018 411076 418011 413908...

result:

ok single line: '418785 413603 418648 419139 41...13 414570 417977 436541 415929 '

Test #21:

score: 0
Accepted
time: 642ms
memory: 74724kb

input:

200000
118922 134567
199816 52066
84326 118291
140839 91527
41156 196216
193057 168156
5712 147301
151841 143708
95806 153816
135331 166094
167087 140971
112587 136986
97546 33542
171749 67249
173810 197325
61841 77212
116769 138505
62675 30261
101896 50402
91780 178503
28880 20528
87860 154449
8267...

output:

13168057510 11173781860 10146494712 16156520832 13448332006 10989071050 10508931040 10037228302 12324541582 10347691962 10028724240 12081412506 11563767480 10187676300 12443176612 10048783240 11774557750 16609608700 15055565506 14134682902 10028318362 11956514056 10158873420 15322067256 11664028056 ...

result:

ok single line: '13168057510 11173781860 101464...110756 18856409772 13401863950 '

Test #22:

score: 0
Accepted
time: 653ms
memory: 70792kb

input:

200000
74212 14285
54279 26014
34653 159417
195912 97270
147173 32677
7753 76853
47200 73990
93075 63990
186243 107173
105569 133096
11068 124684
66637 118271
143298 65684
108858 167243
83551 3112
227 38450
120359 109554
42942 133316
29887 192012
143614 97487
95789 105585
33495 155927
63945 45781
13...

output:

9636839798 7803026188 5944133824 5022351612 5824014810 5466796520 5799132740 5020579868 5118628970 5167194124 5461475062 5089909366 9928608548 5018143302 8863291306 5172571016 6712586160 5054073146 6479682294 5284856118 6274156336 8690429520 8083401824 5218118942 5428913248 9540526484 5044191702 640...

result:

ok single line: '9636839798 7803026188 59441338...48485482 5237756436 7380188354 '

Test #23:

score: 0
Accepted
time: 690ms
memory: 64020kb

input:

200000
92107 93965
159733 109184
192340 76154
84291 151200
22927 32573
60309 166432
136353 52220
46466 195262
169506 58576
155186 181682
129591 45964
5016 99216
173166 72054
186200 95903
105499 17449
196067 122431
177329 57447
66939 50332
67438 62704
184758 103097
13997 9543
159320 119688
67521 1795...

output:

2647717540 2669067610 2536317714 4564900018 4938957828 2523583466 2587289770 4089042968 2538144128 3083739956 2846104828 4939992978 3010058766 2640028282 3303357298 3059661060 3682213356 2518446598 4593066520 3175275992 3500605592 2512952006 2728454602 4496768570 3328605822 3999565194 3852256448 268...

result:

ok single line: '2647717540 2669067610 25363177...80561904 3193035228 3613793802 '

Test #24:

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

input:

3
2 1
2 3
2
1 2
2 3

output:

3 2 3 

result:

ok single line: '3 2 3 '

Test #25:

score: 0
Accepted
time: 670ms
memory: 64668kb

input:

200000
97274 52191
170698 12492
56055 38209
195479 171683
182171 104124
48099 163495
28208 143687
98769 194755
69808 115617
120295 101563
38553 94131
23270 112248
131587 158997
31823 162234
83013 181537
191160 172757
189345 102179
151357 192653
101899 101918
118524 182209
14724 52904
14881 114877
65...

output:

315521802 582270214 374296028 430835082 461750522 547580860 458554994 341017246 385629432 318527132 308318016 304520182 306364072 333253596 574032542 314446098 521022698 407699078 460444652 298495576 297416182 437728058 483072350 552191872 358261158 439148560 390171338 424559912 452883186 322464158 ...

result:

ok single line: '315521802 582270214 374296028 ... 501733906 435471700 498539190 '

Test #26:

score: 0
Accepted
time: 671ms
memory: 62572kb

input:

200000
149275 37122
186803 180793
142343 25474
2212 104891
153840 36431
70840 95284
71111 176237
88737 94284
132867 69692
115881 67641
31109 97047
21627 157384
46886 161629
143575 184545
168978 54964
39205 42574
168223 32975
102385 50620
84750 126621
109786 165166
80248 112638
7161 54171
108145 1160...

output:

156800727 185140211 160861639 163079193 181736213 166433065 169894763 127848699 165191659 128374161 137184613 136296451 122378297 150527067 186298237 142165489 171740743 163923655 144726201 186139667 216535769 143134125 206500761 150034699 166563761 130542877 215959573 147380353 174762851 188816095 ...

result:

ok single line: '156800727 185140211 160861639 ... 198578685 168950583 138834499 '

Test #27:

score: 0
Accepted
time: 4997ms
memory: 178368kb

input:

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

output:

131070 131070 131070 182280 182358 182396 182254 212773 212880 212959 212834 212906 212874 212780 212908 231778 231899 231958 231796 231820 231879 231765 231895 231892 231897 231788 231917 231935 231630 231878 231824 243684 243863 243938 243663 243836 243843 243815 243694 243798 243698 243831 243802...

result:

ok single line: '131070 131070 131070 182280 18...10 262108 262110 262109 262109 '

Test #28:

score: -100
Time Limit Exceeded

input:

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

output:


result: