QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#285350#7936. Eliminate Treeucup-team1303#AC ✓41ms16560kbC++141.4kb2023-12-16 18:01:022023-12-16 18:01:02

Judging History

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

  • [2023-12-16 18:01:02]
  • 评测
  • 测评结果:AC
  • 用时:41ms
  • 内存:16560kb
  • [2023-12-16 18:01:02]
  • 提交

answer

#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int mod=998244353;
int ksm(int x,int y,int p=mod){
	int ans=1;
	for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
	return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
mt19937 rnd(time(0));
int randint(int l,int r){return rnd()%(r-l+1)+l;}
void add(int &x,int v){x+=v;if(x>=mod)x-=mod;}
void Mod(int &x){if(x>=mod)x-=mod;}
int cmod(int x){if(x>=mod)x-=mod;return x;}

void cmax(int &x,int v){x=max(x,v);}
void cmin(int &x,int v){x=min(x,v);}

void solve(){
	int n=read();
	vector<vector<int> >G(n+1);
	vector<int>f(n+1),g(n+1);
	for(int i=1;i<=n-1;i++){
		int u=read(),v=read();
		G[u].emplace_back(v),G[v].emplace_back(u);
	}
	function<void(int,int)>DP=[&](int u,int fa){
		for(int v:G[u])if(v!=fa)DP(v,u);
		for(int v:G[u])if(v!=fa)g[u]+=f[v];
		f[u]=g[u]+2;
		for(int v:G[u])if(v!=fa)f[u]=min(f[u],g[u]+g[v]-f[v]+1);
		// cout<<"u = "<<u<<" f,g = "<<f[u]<<" "<<g[u]<<endl;
	};
	DP(1,0);
	cout<<f[1]<<endl;
}

signed main(void){

#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
#endif

	solve();

	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
1 2
2 3
3 4
3 5

output:

4

result:

ok 1 number(s): "4"

Test #2:

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

input:

4
1 2
2 3
3 4

output:

2

result:

ok 1 number(s): "2"

Test #3:

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

input:

196666
32025 108673
181779 17115
162570 134230
93003 39673
89144 1269
185919 154408
34896 65369
35860 44720
55698 1390
45520 189805
147867 124511
135459 132555
87303 18031
176314 59695
33352 130640
87272 39716
35749 108807
143493 94486
126512 116598
40212 70895
132216 80855
22241 188737
150354 17346...

output:

138182

result:

ok 1 number(s): "138182"

Test #4:

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

input:

192941
180913 51977
128686 137679
118562 93198
60438 181978
39944 140001
169718 122100
146644 138935
22544 124591
113645 112480
128660 133392
9985 102696
4089 62155
4760 3202
116481 17579
59343 141071
81968 156270
5544 186622
117322 35780
127098 110151
148427 70933
2244 44243
3778 176132
181512 1583...

output:

135478

result:

ok 1 number(s): "135478"

Test #5:

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

input:

194488
130963 189387
157318 154522
38501 173612
180088 154173
62179 130568
174923 60255
82848 92742
77176 187920
52859 194392
174926 119679
50715 29603
40935 171733
40347 99095
156851 93563
24220 153338
179719 163771
30534 145015
194261 85487
17914 48210
169737 72603
62083 78874
45506 185776
30650 1...

output:

136847

result:

ok 1 number(s): "136847"

Test #6:

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

input:

188262
184858 11141
165075 93016
74608 149656
148389 139491
74045 25669
173575 32275
21056 101384
141208 109614
10808 44201
94002 120593
113484 106927
68551 141389
6272 22586
94424 54385
120255 172038
8651 27548
187509 134575
128590 105430
68605 61164
70994 140259
147498 83053
46414 77522
72222 2636...

output:

132042

result:

ok 1 number(s): "132042"

Test #7:

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

input:

182747
35622 146780
16901 148028
49576 52508
22285 168671
34153 157628
22497 75161
7123 59296
86920 53643
105329 159277
153614 46344
3310 175828
7801 663
157619 35549
120965 11545
12223 42549
152735 103392
180120 170333
146866 83056
106574 139065
129763 44082
53277 168101
29933 168120
119516 110321
...

output:

128278

result:

ok 1 number(s): "128278"

Test #8:

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

input:

196394
61810 86037
48586 74422
194576 105852
159073 83939
89353 79033
50536 184437
186672 167787
131449 157876
55795 173068
163116 183854
44171 30780
186241 181489
8207 20801
67830 143667
126718 135860
150189 32560
40221 13340
102548 82515
63452 40945
49204 116866
72538 119860
150 167512
92813 14968...

output:

137749

result:

ok 1 number(s): "137749"

Test #9:

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

input:

185370
159713 33643
69685 120062
5446 3709
104647 172504
91310 128259
77971 86098
36256 160030
135027 164556
48691 40367
72267 141580
63542 79648
111187 148090
25947 170242
101361 148073
121971 143652
76584 136869
108910 167398
22904 92526
125303 171903
24158 145220
113709 77096
27889 78536
137686 1...

output:

130122

result:

ok 1 number(s): "130122"

Test #10:

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

input:

188722
86256 105137
58173 72685
56378 71702
171316 95387
60076 187934
104998 72069
116236 82471
79994 152080
54933 133325
122542 88588
118016 185297
147091 80970
116303 83351
38837 71397
171714 18018
61180 111054
87565 40842
85634 25465
119305 10308
34370 105555
101280 140246
21620 123848
142336 631...

output:

132356

result:

ok 1 number(s): "132356"

Test #11:

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

input:

182488
81554 102751
93180 59855
133059 146808
63751 122395
148218 48996
7417 62114
14283 168283
83890 120897
111497 31294
179906 129527
14822 58843
92530 52235
182305 43200
180428 134082
108883 170433
29397 13273
172397 105592
142899 76080
30038 5678
42564 67594
33341 143107
46327 141787
94986 16303...

output:

127919

result:

ok 1 number(s): "127919"

Test #12:

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

input:

184568
31149 51024
176606 113048
139955 5137
84361 18522
40104 104722
61578 147568
64213 129042
112825 27784
151664 92711
29593 101922
110479 162124
97496 19053
179559 63746
115089 87401
93927 132762
32781 69746
172423 11106
9582 114514
63089 55576
74236 158196
77204 96742
11131 161226
111563 5911
1...

output:

129550

result:

ok 1 number(s): "129550"

Test #13:

score: 0
Accepted
time: 33ms
memory: 14688kb

input:

182762
18299 3108
95039 28248
55011 87567
35417 145308
87699 34875
104960 40698
144442 123632
95104 28069
163124 88237
166648 174891
35063 114258
60064 25277
84766 93308
157789 117696
93909 174392
152221 114035
114685 1434
117535 51520
57270 48083
118082 113388
33251 178045
37680 180643
101863 10885...

output:

127582

result:

ok 1 number(s): "127582"

Test #14:

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

input:

190566
84570 104400
4072 130857
10158 161484
176493 115993
10223 58502
145123 126263
41997 184456
178745 97123
70469 50767
174258 148602
129269 64858
144420 17226
96063 5468
101084 30099
99773 161713
11734 100672
30019 156826
72677 121565
81812 78723
60108 149445
33646 26934
180116 128276
60172 1614...

output:

133188

result:

ok 1 number(s): "133188"

Test #15:

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

input:

185805
113458 97379
126910 94613
43391 78601
142361 149299
101799 24512
169071 104550
99964 166137
35587 103107
177073 35715
185468 74645
78061 55514
107263 137446
134774 15612
98078 160945
134837 93755
106384 45722
55275 155127
33356 79175
91463 177155
135305 7333
132471 42596
59741 90374
120086 68...

output:

130296

result:

ok 1 number(s): "130296"

Test #16:

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

input:

189616
187053 170807
76598 87530
2390 9767
68352 24645
131553 111726
111335 109277
138620 120407
88864 141500
178792 171218
47990 146531
160509 142890
112602 185237
37407 128487
41088 185274
99896 125976
92509 150701
46858 147703
156696 92520
63847 73941
93080 64040
24396 67703
95116 114876
5135 977...

output:

133160

result:

ok 1 number(s): "133160"

Test #17:

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

input:

191286
105971 19632
10996 25847
25282 28420
183544 97181
18473 49889
168836 96488
37982 45309
21633 50182
44255 78888
150959 35667
184216 159199
156437 51798
28837 124118
112857 125249
95261 452
159821 53354
161903 33319
146502 108319
22886 180657
82604 176644
158730 93997
148191 61050
124670 89614
...

output:

134133

result:

ok 1 number(s): "134133"

Test #18:

score: 0
Accepted
time: 33ms
memory: 14928kb

input:

187045
110439 112921
45626 63433
110683 90422
151825 45394
9503 36342
169675 124267
18249 166313
144687 62838
160851 134645
41634 185796
24707 118930
137591 162714
136198 41303
81600 179522
36451 142836
37447 146000
9456 4077
2160 132551
181746 158760
154177 176425
15998 170392
152174 169445
129821 ...

output:

131177

result:

ok 1 number(s): "131177"

Test #19:

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

input:

192776
56579 92505
142228 71936
133037 65037
31364 43548
105970 116621
53559 151883
137701 11490
93447 12703
96669 38361
146497 170708
119729 132722
29407 41050
52983 114591
100535 47162
39538 1648
42201 151295
125219 43529
134839 143177
88636 65518
88038 158822
173785 135607
2784 21643
25405 184860...

output:

134923

result:

ok 1 number(s): "134923"

Test #20:

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

input:

180877
128784 136428
167314 160649
134588 30761
112773 158742
35367 105377
19434 173240
109432 90922
31114 31888
111883 28546
32844 24459
80631 157565
16533 157122
145970 24744
135355 79513
9975 74453
133006 135797
159365 156875
98864 158086
22541 157415
70335 112367
37958 88967
124020 173802
6613 1...

output:

127004

result:

ok 1 number(s): "127004"

Test #21:

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

input:

199933
147018 162617
104391 30174
17671 16436
187517 80452
133281 138783
31387 83022
193493 83965
122547 114862
87946 116455
90156 105153
93870 138748
80737 123371
21132 101192
146592 128608
167381 42220
13458 98456
159005 105848
123562 85501
131638 165859
96210 179443
126258 56393
166160 158093
582...

output:

140126

result:

ok 1 number(s): "140126"

Test #22:

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

input:

189616
153440 83824
5279 103010
44363 48101
57444 132250
19388 34452
33606 169223
48912 162247
37076 167356
183998 174384
95725 182205
9252 67438
27856 165269
84272 103418
151633 8101
3836 9639
104025 19583
138454 154256
150522 188445
139855 91623
140257 123098
35319 60182
3095 151624
72241 159651
1...

output:

132902

result:

ok 1 number(s): "132902"

Test #23:

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

input:

187966
124422 120237
41297 76878
39168 166047
146635 32636
68825 35235
170690 138580
5753 64764
109674 179631
98532 72879
118666 173096
121887 160261
20913 79971
122535 97463
187509 39733
6420 64379
159638 117539
139064 98951
45714 35466
123802 116646
96144 22482
79424 110030
144381 60667
74003 4685...

output:

131984

result:

ok 1 number(s): "131984"

Test #24:

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

input:

195427
102360 53261
77068 109097
33359 44559
158062 84902
103485 142229
192108 115351
19514 50076
56920 98960
40679 117899
73045 126157
84784 108536
58348 20057
60121 74390
167516 92559
145546 104954
12509 93907
86593 118727
102761 68107
38621 190708
104181 105825
93608 180086
84651 101889
178493 12...

output:

137243

result:

ok 1 number(s): "137243"

Test #25:

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

input:

194457
71973 21190
83031 32560
75064 7574
143984 174042
1379 58266
65286 191144
3512 153476
148478 111075
124463 110676
137215 97689
40012 191801
90592 5481
102798 75152
172405 49024
181896 75753
155385 117242
42787 180989
14336 3663
7945 189035
84546 47674
77898 46138
99500 180980
172093 16959
1249...

output:

136371

result:

ok 1 number(s): "136371"

Test #26:

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

input:

181281
130312 73298
27922 74952
107707 138665
112209 101796
137636 129142
57122 161526
179581 85448
48243 151919
124986 129481
5669 14563
64355 108085
134822 138364
139232 181038
169582 99094
78614 173772
101280 173054
45859 84000
40456 151509
285 11166
101090 13170
102179 128598
88845 173417
76023 ...

output:

126861

result:

ok 1 number(s): "126861"

Test #27:

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

input:

181259
101988 46464
16233 177463
52604 18157
50214 131749
142074 27114
164750 63936
104690 120180
153872 159521
32458 144211
81255 26862
158319 169249
3537 30545
160341 9486
162601 145871
81219 61973
178462 56757
175213 90465
156287 110143
180533 127284
10992 135720
95315 161227
50847 80087
151032 4...

output:

127123

result:

ok 1 number(s): "127123"

Test #28:

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

input:

186452
175890 93742
99120 142723
176528 139543
106838 76209
185054 33120
4612 4097
151877 133699
125852 91409
175120 175635
140561 7235
179214 55
105575 164386
154700 46974
180499 144537
110236 22456
183408 79977
33347 173677
24139 142492
16780 96704
155938 177439
126691 143567
30874 122832
122325 1...

output:

130780

result:

ok 1 number(s): "130780"

Test #29:

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

input:

185168
18 6633
148947 23690
133893 61896
30132 142697
19908 77234
38291 70750
37756 16606
128335 172773
43977 142646
144602 16759
67949 45340
109971 145612
59491 80922
13326 54508
162812 56803
75579 65177
20539 127836
52295 14830
85165 127422
161254 175648
1056 10295
38957 48841
3711 161466
99006 17...

output:

130153

result:

ok 1 number(s): "130153"

Test #30:

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

input:

180651
68085 86416
15853 111869
93142 37245
92718 17175
67277 11170
157194 43075
137609 141978
71647 123362
141824 136564
171569 136045
111240 93518
156403 78100
94204 163598
124301 153019
148291 112842
178931 160380
61798 161102
116305 211
146493 85802
109745 108308
158635 50459
178985 161957
10771...

output:

126774

result:

ok 1 number(s): "126774"

Test #31:

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

input:

197731
139438 76555
111803 164383
113379 46005
49152 186031
171077 162871
14020 158089
162130 26290
129986 93677
44117 64997
146652 155139
189626 158358
159214 129589
154955 196499
47604 82093
62918 174689
129423 7608
162359 12528
3651 68890
197477 164536
115266 40257
89565 114552
158132 125321
1224...

output:

138938

result:

ok 1 number(s): "138938"

Test #32:

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

input:

188214
76720 155498
159965 171585
9257 172889
87300 90306
113157 4474
136750 115637
85439 19052
73307 23322
14224 115303
75924 71871
115899 20146
91619 166229
100148 55620
5593 114737
89046 117479
75283 93603
52087 169631
175612 67790
23232 74655
162783 98805
169957 107605
149763 168675
150104 18771...

output:

131985

result:

ok 1 number(s): "131985"

Test #33:

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

input:

196885
138092 96416
110184 161437
70946 62257
196515 30637
190504 138740
91203 170007
127208 15794
40612 24099
62495 97708
169654 130825
193576 136926
96840 68981
102206 20892
156109 87396
135261 182371
31459 69121
160777 90
26517 32257
9321 71588
89476 15309
23792 73917
188576 21957
166363 112301
1...

output:

138065

result:

ok 1 number(s): "138065"

Test #34:

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

input:

195426
101496 94483
118527 35953
172166 119960
112394 187097
34523 142773
12468 138196
65034 84769
121396 84630
1983 71535
27664 172791
157715 17030
77861 7351
36353 141438
142263 61589
63576 154990
34943 161342
108713 65231
181198 188579
129566 127819
148728 58678
22261 162314
156071 73777
73339 12...

output:

137433

result:

ok 1 number(s): "137433"

Test #35:

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

input:

184833
181406 116392
149165 146953
114342 68883
151733 41769
24394 74357
159540 172571
78385 46549
70443 5514
168322 90439
160524 111897
21800 136366
62440 3727
116747 30110
13459 124885
155495 146887
174023 98698
47486 93825
7203 130518
107256 165817
127329 61019
49685 169691
17990 149013
13780 266...

output:

129429

result:

ok 1 number(s): "129429"

Test #36:

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

input:

192756
18595 36647
163561 57347
18632 182884
26424 137171
141937 185487
37328 10959
60217 99602
21073 95389
70632 131966
189655 145390
69730 39279
123172 86142
181978 67334
115618 20185
188030 190204
64767 155858
60596 56647
88154 1910
74536 111458
23550 189929
23526 108155
160370 13796
165233 13324...

output:

135222

result:

ok 1 number(s): "135222"

Test #37:

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

input:

198645
47596 195438
167324 161923
130106 70017
196692 161158
95804 108239
54825 144293
192633 190259
169231 56756
116622 15928
138601 41184
106782 13000
37786 149139
176367 90503
81664 158014
3422 2127
91303 51848
23554 14511
155861 82474
52269 7668
4704 168300
19531 141757
13806 134231
55754 55317
...

output:

139584

result:

ok 1 number(s): "139584"

Test #38:

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

input:

192323
144158 36586
63783 61842
81932 72932
126074 118491
36261 127168
108651 155395
164852 119186
155913 170249
59632 100885
142347 119117
137183 188884
104024 90454
102542 137693
6067 115706
56351 61254
129236 114090
141416 112234
112443 187418
101417 76547
74423 47133
32479 175883
74039 25186
506...

output:

135310

result:

ok 1 number(s): "135310"

Test #39:

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

input:

184432
155851 116256
4156 811
140225 64599
174910 144009
57064 89591
177721 143696
110292 134287
48126 58962
63267 146555
137426 109007
143238 106988
64439 47239
635 147815
102973 19358
179284 108742
161986 67205
147091 151317
74177 30964
149957 17093
30646 135551
92940 36875
121177 4148
21449 16993...

output:

129587

result:

ok 1 number(s): "129587"

Test #40:

score: 0
Accepted
time: 33ms
memory: 14804kb

input:

181997
86977 80492
114425 118368
34653 85838
132375 98118
65123 91823
123932 58314
177862 34934
11081 148050
149858 100694
103815 55042
51158 180424
74694 47564
45302 126058
178751 93013
117921 88750
56719 11743
115429 38369
138049 46603
171955 53199
99491 121538
4794 164372
44587 152447
68296 14048...

output:

127489

result:

ok 1 number(s): "127489"

Test #41:

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

input:

184975
6392 6232
113651 11046
86669 173444
80992 53160
145867 22082
145467 68858
35297 34758
24104 145410
51781 181698
45376 95507
147314 57398
23081 22368
158271 83946
19928 173616
95926 134454
81282 100015
180165 103128
170085 51121
73735 148571
56588 118615
153975 111711
158641 175307
110328 5460...

output:

130025

result:

ok 1 number(s): "130025"

Test #42:

score: 0
Accepted
time: 33ms
memory: 14920kb

input:

184240
28540 125833
181984 77306
37674 122144
139905 178778
119848 138773
124367 87924
131600 17454
46555 30247
34304 155014
149456 72330
129381 16248
92807 87096
54796 11469
11156 57126
168766 108960
176070 69828
34475 76903
51330 95300
41364 89579
88517 174572
90756 115798
139941 78413
131663 1460...

output:

129326

result:

ok 1 number(s): "129326"

Test #43:

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

input:

180363
129912 140478
102263 146335
69753 3324
51519 138086
47679 88884
77129 93170
108451 117199
108866 59259
140116 66642
87454 126276
99444 171219
28035 106924
146206 152600
106247 65143
122115 127248
2633 174589
165695 31661
19242 123030
178035 102780
12533 97637
61377 19381
75063 3245
117519 197...

output:

126903

result:

ok 1 number(s): "126903"

Test #44:

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

input:

191382
129945 72768
22026 1394
178909 20275
143552 137394
141553 56922
107878 11680
142751 4778
34962 104077
29864 2034
129689 63083
183419 143090
62478 36328
71795 115088
141561 56018
46498 78907
182641 91719
113027 167284
65742 142161
169804 136729
61108 82929
126709 27080
136527 51157
80108 10953...

output:

134286

result:

ok 1 number(s): "134286"

Test #45:

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

input:

197262
196511 164355
187925 68487
84376 137234
11455 101684
15440 76787
98568 129454
64916 59620
53744 100029
120648 98284
141136 16569
130863 15671
118324 126290
34985 89818
130621 34050
84740 39846
102012 56152
155810 171331
1639 58032
122679 68419
80233 147715
75914 54471
40300 124941
1995 151944...

output:

138336

result:

ok 1 number(s): "138336"

Test #46:

score: 0
Accepted
time: 40ms
memory: 15724kb

input:

198422
27085 97439
4088 81159
159223 187447
116183 90306
149687 140632
16883 118412
166801 158017
109442 193198
175862 26633
40701 146182
118535 26568
18460 84603
158812 146625
81683 2666
32981 74964
42286 158158
50632 63418
139466 126634
139613 151038
49110 44803
84867 9497
156702 148710
59023 9286...

output:

138928

result:

ok 1 number(s): "138928"

Test #47:

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

input:

184046
2628 131379
125696 182302
117930 27329
103027 29877
67949 145604
3763 57066
87143 77130
36358 127958
179615 138377
43761 11146
2357 83623
159944 176593
180280 3812
164365 130336
93511 95758
181045 117240
70522 114315
10985 120218
76369 137433
157935 55460
132155 129582
50719 120274
89315 2052...

output:

129235

result:

ok 1 number(s): "129235"

Test #48:

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

input:

181383
85717 139550
173615 108970
103402 100383
95815 74971
135741 62330
107539 13716
105379 91375
3101 96449
73506 90724
58974 7054
178963 25683
181053 95149
117126 54907
174834 75291
88795 7464
47796 136304
103276 49976
38137 11177
96051 101244
125192 112656
14081 30173
10187 181361
178073 160858
...

output:

127785

result:

ok 1 number(s): "127785"

Test #49:

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

input:

194419
50898 51438
130207 166652
156975 141551
143814 22142
154873 161043
189750 150419
6164 44345
147139 14577
73172 149829
9013 50896
98580 29119
7193 123105
28078 147359
176870 159303
171218 66101
109834 137756
46503 164667
156060 134222
84237 147484
151507 44114
106452 74716
180211 77456
73868 1...

output:

136415

result:

ok 1 number(s): "136415"

Test #50:

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

input:

187759
44749 43267
37786 36128
13286 13137
89433 88287
177003 171336
102273 103232
50033 50248
71464 71103
12217 12031
38816 38506
122378 120781
169833 163892
47033 47220
36316 36056
3951 3956
114469 114017
115142 114607
70028 70098
40027 39438
154558 163669
151197 153203
25200 25286
166109 166000
9...

output:

131288

result:

ok 1 number(s): "131288"

Test #51:

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

input:

191647
91567 1680
63372 931
36054 275
1439 21026
2302 38431
245 29011
135353 3636
637 71179
127853 2508
161919 4829
142519 2167
100576 993
63780 3638
25793 346
153 92939
36120 3499
2998 58417
19 61075
7005 102334
116453 43
984 159729
151670 3658
2144 36098
405 167305
14879 109231
392 47226
53730 652...

output:

323993

result:

ok 1 number(s): "323993"

Test #52:

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

input:

191954
117395 120512
176073 179358
176316 182223
97150 99339
146707 148988
145495 145407
118836 123733
103303 99233
104653 104104
163885 162374
142975 149899
106380 108229
97448 102303
108437 110453
153241 147102
16406 15854
52396 52491
47756 48489
52113 51976
78825 76423
56933 56401
160365 164583
7...

output:

134845

result:

ok 1 number(s): "134845"

Test #53:

score: 0
Accepted
time: 18ms
memory: 15656kb

input:

184663
1522 44000
171200 2329
17 167948
223 45301
47 94452
3573 101850
6950 160784
13108 166745
165620 8534
4512 101087
2461 67098
12862 850
3150 125168
2059 172873
158143 1884
75098 2461
261 156175
57554 2205
139121 2735
3555 86256
409 59251
78984 376
76 26063
109373 1900
3699 100603
3905 128890
51...

output:

323378

result:

ok 1 number(s): "323378"

Test #54:

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

input:

184512
103475 436
183 49148
142830 3824
2838 95180
1846 154950
201 28733
2404 162503
175208 4343
844 53540
2484 159541
2212 163665
184358 1227
164769 1944
120668 2650
150002 1488
76958 1543
68745 1212
1561 126069
91722 1699
87290 1299
105622 954
23529 75
4416 176208
54449 80
926 133737
219 39756
10 ...

output:

340437

result:

ok 1 number(s): "340437"

Test #55:

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

input:

187013
73244 556
7548 128864
272 44408
11282 12
3610 328
174355 1126
33332 1825
5809 89101
24016 176160
2220 154547
46 127238
12093 166256
3823 174627
138565 4589
790 58555
101275 4766
1222 96757
110544 1265
1525 80377
6771 59399
4381 160346
83384 13000
6038 92554
43636 723
10441 67955
390 95996
174...

output:

308434

result:

ok 1 number(s): "308434"

Test #56:

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

input:

192154
481 74536
3697 105248
3289 159883
174220 3302
7050 75989
10827 135465
2038 105509
1651 183059
344 104000
123909 3757
3125 95221
462 28821
109030 46
1916 67201
5093 130382
2234 7
197 80804
1006 133395
570 137698
75981 1977
576 74209
83514 2780
31424 566
946 26746
1588 138592
121 9331
31569 264...

output:

344108

result:

ok 1 number(s): "344108"

Test #57:

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

input:

193293
93290 371
6921 262
141687 479
2393 148573
2006 153967
1133 90603
243 73897
1541 103362
115284 194
142670 2126
1046 193014
3690 190298
62295 1265
1809 66888
87422 274
120062 206
132 82454
1290 134495
2718 84419
1572 60341
40507 550
106178 116
81359 222
187523 2965
76252 180
64288 482
75454 134...

output:

360522

result:

ok 1 number(s): "360522"

Test #58:

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

input:

197390
78583 732
134665 850
125088 3208
133840 5010
47 12562
2 4173
637 173561
32453 81
19 18617
428 79488
823 47678
112073 2310
137066 2983
308 79621
5776 42
3645 152170
193866 1507
2059 182599
162221 4457
160011 1040
98 31326
978 25805
10 143751
76 168838
131134 5708
315 110242
118532 751
1788 157...

output:

360214

result:

ok 1 number(s): "360214"

Test #59:

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

input:

183955
136572 16884
113231 4131
4380 21075
122400 3811
175 22966
16784 126698
13022 89371
33821 158742
97108 7028
368 155998
117608 22563
122118 13033
657 18386
15742 1760
17092 180865
70231 2854
159710 837
150977 10896
8593 113075
1881 164939
5272 41978
123051 29776
6 272
95299 2768
11606 58009
161...

output:

267959

result:

ok 1 number(s): "267959"

Test #60:

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

input:

192468
121528 5485
431 167900
77892 1083
113 36582
2818 137246
566 116442
146441 13946
399 32714
3788 133444
888 175992
2142 178254
14995 226
120845 5020
159604 21278
38076 492
70938 1768
188174 8958
526 86743
98749 196
1950 153320
838 9788
188312 4724
161217 1780
3177 126712
3316 59472
145 18929
29...

output:

339057

result:

ok 1 number(s): "339057"

Test #61:

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

input:

185177
147190 4740
73441 25931
16141 41654
1839 127874
13916 104986
997 6462
20183 72668
22550 1482
278 89059
74112 1885
111553 5304
63806 160030
34588 66238
2141 40311
71381 57845
17666 253
43999 179570
38625 152568
61 2338
122056 41766
154197 22344
7418 179724
23642 166896
50246 15390
62550 145553...

output:

189376

result:

ok 1 number(s): "189376"

Test #62:

score: 0
Accepted
time: 23ms
memory: 16008kb

input:

189075
108036 563
3298 151208
184846 1037
142075 803
178795 2576
72970 5595
1286 87783
2579 127547
3009 132961
1864 16
42858 686
1443 19777
1078 172289
131493 3658
354 19034
1317 129714
120692 2394
86181 2256
3253 157008
60220 2308
147795 7028
511 162707
181333 1815
104665 78
1902 125603
88256 1454
...

output:

341751

result:

ok 1 number(s): "341751"

Test #63:

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

input:

184271
149 17898
34814 664
556 183843
137448 4960
1040 24102
167011 9993
152423 4287
9867 932
118624 1380
29839 5429
7182 343
4934 153067
41915 43
170558 1895
920 118044
87046 1734
16446 164241
56 65787
4710 558
128 18085
54186 621
4654 58992
1555 119426
183778 7465
3726 98940
1597 94293
34271 2454
...

output:

311422

result:

ok 1 number(s): "311422"

Test #64:

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

input:

188122
62644 55097
27450 28717
112849 155753
155549 127775
18845 15426
90203 107015
56760 61599
112073 106809
40254 53295
168500 137916
121824 126230
133388 115135
24933 25062
48494 44495
184415 181384
127766 125073
143902 182298
122710 119153
65651 65576
98521 107540
173071 158917
184690 144520
122...

output:

133079

result:

ok 1 number(s): "133079"

Test #65:

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

input:

182822
35210 34679
143809 141952
122843 123431
117891 118441
96017 96856
46580 46294
3558 3485
24724 24609
59458 58859
105713 106128
71176 71605
96050 101091
11219 11217
2754 2758
36939 37072
104105 107020
85396 83787
10134 10118
79189 78958
6643 6455
47414 45882
57140 56820
168919 170972
152941 153...

output:

128218

result:

ok 1 number(s): "128218"

Test #66:

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

input:

194907
101747 101042
149282 150707
45564 49836
79428 72798
75560 69377
167483 167731
87825 87035
105416 109271
185711 189317
17781 17449
37926 37268
25517 25992
116897 117687
169720 157193
90635 90969
64857 64964
134645 135208
162796 166040
35382 35467
135553 139401
7979 7761
26910 27254
61636 62284...

output:

136980

result:

ok 1 number(s): "136980"

Test #67:

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

input:

183017
16132 79
169814 140
1188 22829
3135 108222
3587 169291
5587 76334
10852 116236
4730 130424
1887 29680
123694 1721
164374 1243
2273 163060
71811 1201
9905 78
199 40180
1304 33798
872 21866
38458 529
3942 137543
1963 50774
55117 213
51277 748
2577 105180
758 82390
2456 84657
784 34532
985 15975...

output:

323506

result:

ok 1 number(s): "323506"

Test #68:

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

input:

183364
142428 3326
113930 8129
1663 67831
2501 103515
73087 8841
31050 1585
132545 9699
10562 1568
4379 62686
84777 5526
3469 163782
134447 15929
2500 102661
166015 1911
4732 83188
71235 2106
4278 63223
3527 117126
141698 3061
26575 328
4271 150869
716 47269
131893 8219
5182 174152
17829 252
72870 1...

output:

318053

result:

ok 1 number(s): "318053"

Test #69:

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

input:

182126
171365 169032
172701 170875
40591 41309
63770 65639
17141 17140
88280 90975
25248 28670
16867 16553
112463 113700
49963 52519
107769 103654
101755 102846
16772 16969
78404 79992
66282 65175
54448 53129
55105 52438
104129 106561
116429 117584
69577 73049
127269 131283
11026 10921
180276 178303...

output:

127921

result:

ok 1 number(s): "127921"

Test #70:

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

input:

199619
48104 48940
193081 196422
105398 106121
55159 55315
164795 173558
176831 171598
137089 138759
152349 152922
198966 198673
184324 184059
60289 60284
161212 160810
182752 182608
33889 33919
38046 37927
151314 151064
42666 42670
104714 107858
124054 123799
50205 49625
158076 158480
33980 34412
1...

output:

140341

result:

ok 1 number(s): "140341"

Test #71:

score: 0
Accepted
time: 25ms
memory: 16520kb

input:

198299
124046 116
509 92350
97397 915
179 72929
187681 1407
27378 465
1032 30379
157539 359
182000 87
144 5852
2256 84613
1550 117325
166277 222
144715 4147
191975 2816
9795 63
484 94640
1492 146918
1540 97181
98880 2387
2724 176207
720 133879
183071 152
184392 7217
157 16088
384 45907
450 29194
192...

output:

372646

result:

ok 1 number(s): "372646"

Test #72:

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

input:

194282
515 47366
196 14163
75276 920
1 11162
90 17409
212 17386
26528 85
1651 189827
3216 170524
1415 90426
55820 672
129 69923
3220 78740
81046 62
407 164242
158390 3356
57304 1373
2169 3
146861 255
39926 151
120739 2
1451 148448
46 31870
1037 132521
43820 124
324 193201
875 119937
650 119438
18538...

output:

366184

result:

ok 1 number(s): "366184"

Test #73:

score: 0
Accepted
time: 18ms
memory: 15592kb

input:

182518
20955 433
1709 143864
90949 560
121613 171
146651 279
664 93320
3872 108006
35361 2215
150279 388
13196 82
143683 520
446 40121
182370 8614
94889 739
79 52259
150372 4287
728 61387
80648 3319
1329 160725
2457 154861
65 27932
146168 675
84518 3348
324 15101
2495 84090
114159 1435
742 57192
529...

output:

331112

result:

ok 1 number(s): "331112"

Test #74:

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

input:

181800
128592 129797
53088 55907
61983 60527
49261 49622
3064 3035
170232 170569
150215 159510
84509 85583
169072 168891
111255 106651
148238 154863
49542 50536
103853 107443
36905 37092
52352 54424
33765 32387
86817 86541
125460 124521
136251 143853
63948 62603
51351 51802
158534 161570
57916 58021...

output:

128118

result:

ok 1 number(s): "128118"

Test #75:

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

input:

196910
92534 100689
34166 33624
59034 59123
140344 116785
76194 62802
126240 119594
12177 11099
76730 66645
73 87
34044 38290
168519 160687
60132 60936
149978 172693
29533 26115
155688 165426
35552 32041
144314 156931
49417 48703
119271 122606
58771 59790
157879 161364
183916 159438
102322 109527
57...

output:

139117

result:

ok 1 number(s): "139117"

Test #76:

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

input:

199974
36391 36375
74301 75782
56729 60118
51284 51329
135854 136249
39920 39933
64702 62888
48795 49146
152358 152237
93493 93487
42776 42603
44357 43391
119950 119528
119975 118475
18600 18931
156991 162005
89584 89042
46754 46765
102352 100316
42691 41893
63903 63849
14470 14156
8567 8602
49761 4...

output:

140163

result:

ok 1 number(s): "140163"

Test #77:

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

input:

1

output:

2

result:

ok 1 number(s): "2"

Extra Test:

score: 0
Extra Test Passed