QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#186781#5157. High-quality TreeForever_Young#AC ✓167ms28432kbC++141.2kb2023-09-24 11:40:272023-09-24 11:40:27

Judging History

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

  • [2023-09-24 11:40:27]
  • 评测
  • 测评结果:AC
  • 用时:167ms
  • 内存:28432kb
  • [2023-09-24 11:40:27]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long double D;
typedef long long LL;
const int N = 222222;
vector<int> e[N], vec[N];
int fa[N];
int main() {
	int n;
	scanf("%d", &n);
	for(int i = 1; i < n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		e[a].pb(b);
		e[b].pb(a);
	}
	vector<int> q;
	q.pb(1);
	for(int op = 0; op < (int)q.size(); op++) {
		int v = q[op];
		for(int y : e[v]) {
			if(y != fa[v]) {
				fa[y] = v;
				q.pb(y);
			}
		}
	}
	for(int i = n - 1; i >= 0; i--) {
		int v = q[i];
		static int s[2];
		int ns = 0;
		for(int y : e[v]) {
			if(y != fa[v]) {
				s[ns++] = y;
			}
		}
		if(ns == 0) {
			vec[v].pb(0);
			continue;
		}
		if(ns == 1) {
			vec[v].pb(vec[s[0]][0] + 1);
			vec[v].pb(vec[s[0]][0]);
			continue;
		}
		if(vec[s[0]].size() > vec[s[1]].size()) {
			swap(s[0], s[1]);
		}
		vec[v].pb(vec[s[0]][0] + vec[s[1]][0] + 2);
		for(int i = 0; i < (int)vec[s[0]].size(); i++) {
			vec[v].pb(vec[s[0]][i] + vec[s[1]][i]);
		}
		if(vec[s[0]].size() + 1 <= vec[s[1]].size()) {
			vec[v].pb(vec[s[0]].back() + vec[s[1]][vec[s[0]].size()]);
		}
	}
	printf("%d\n", vec[1].back());
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

6
1 2
1 3
3 4
3 5
5 6

output:

1

result:

ok single line: '1'

Test #2:

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

input:

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

output:

3

result:

ok single line: '3'

Test #3:

score: 0
Accepted
time: 150ms
memory: 28068kb

input:

200000
167246 158246
40931 40296
178588 27974
35171 899
4204 163250
101422 9230
55420 93371
16012 140142
28866 154497
33519 180725
50361 52348
46923 175364
126599 169575
15138 34958
164256 64770
63123 130169
154172 168301
127476 54744
199964 81879
173765 69220
178225 73653
59861 46415
138112 17507
8...

output:

199998

result:

ok single line: '199998'

Test #4:

score: 0
Accepted
time: 167ms
memory: 27988kb

input:

200000
144434 24107
75087 108465
38670 156657
31235 30143
40544 44213
51188 21788
170574 164351
14169 155909
120876 119956
196361 140453
197958 142813
23944 62568
12098 71652
162226 122184
123783 86178
70076 115586
74439 94246
83296 36713
182500 16937
174946 154091
97484 194764
179943 61793
114439 1...

output:

199998

result:

ok single line: '199998'

Test #5:

score: 0
Accepted
time: 131ms
memory: 28272kb

input:

200000
42469 8516
3910 143673
129125 150433
170053 160404
147325 66173
130784 195620
183508 43943
90940 88012
187183 803
139576 36677
190280 71191
107959 177664
14308 20402
93449 130555
80315 75413
178265 104526
4428 8875
151397 91172
181321 47276
105060 81973
196326 19584
44364 56143
187070 195424
...

output:

199998

result:

ok single line: '199998'

Test #6:

score: 0
Accepted
time: 82ms
memory: 23368kb

input:

131071
94531 87688
119005 53065
70725 126770
61026 82294
114384 270
98205 38915
61461 14652
123122 36872
37639 52311
17774 89648
79899 59785
6033 52465
15449 93250
43849 18174
2665 82543
26740 15199
71645 14339
45549 119270
22896 70677
126250 23614
5796 85715
92715 25280
119740 8911
17923 5547
47703...

output:

0

result:

ok single line: '0'

Test #7:

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

input:

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

output:

0

result:

ok single line: '0'

Test #8:

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

input:

75026
12155 64806
40053 74785
70103 1220
72989 33966
74199 66365
52024 24358
54545 52118
52572 28566
68873 41146
10161 67848
41221 63589
72291 44013
51515 14784
12150 33009
3919 23413
61773 13741
21172 17759
27774 65766
58702 13619
11690 19263
45469 30662
33296 45184
51641 13235
11413 52734
74437 57...

output:

2

result:

ok single line: '2'

Test #9:

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

input:

10947
7184 5103
1433 10766
3794 8428
1438 8926
2493 7796
6753 7135
3304 4497
9148 8680
4013 2259
3067 8641
2809 9523
9557 2452
8392 3411
1121 6418
5150 133
8893 3701
7864 3044
7152 705
3856 5325
10943 4760
9792 7866
6959 6282
1120 7627
2952 9675
10407 9119
2489 1131
907 4948
4175 3572
4178 337
226 7...

output:

2

result:

ok single line: '2'

Test #10:

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

input:

8375
5605 5852
7762 3219
1669 4378
341 6410
1502 1920
706 8356
5088 5723
1326 6305
2433 5341
5185 948
7639 5745
6173 7572
4736 7204
8081 3452
2414 6798
156 7332
6627 2209
876 5078
2666 292
5041 7782
7118 807
6897 5220
5865 1273
6546 1506
4306 7980
1119 6488
4795 5942
6219 7729
8119 1572
4027 4817
46...

output:

701

result:

ok single line: '701'

Test #11:

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

input:

19450
13860 10518
15222 9423
8628 4061
13172 14144
10621 1876
14867 11492
5902 19300
11313 2895
2777 6935
6948 18381
13897 14220
11979 19134
5771 10820
19025 16787
8909 7140
10163 19125
4204 5969
8802 3293
11379 17457
4788 6749
14771 10567
5201 18207
3410 7595
12521 4698
19184 15244
10662 7902
16998...

output:

732

result:

ok single line: '732'

Test #12:

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

input:

199999
42470 186792
84838 99410
115027 161613
35565 77810
72472 47859
180671 162382
32852 67468
75811 198709
124926 126090
54877 26903
165267 13544
8081 157453
152632 92738
145016 76659
74572 183100
116308 42324
140949 129632
170934 122224
10244 34160
88908 198457
124270 136554
190537 124534
137981 ...

output:

199994

result:

ok single line: '199994'

Test #13:

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

input:

199999
32647 44026
42853 57810
175394 58242
95892 8293
2439 15285
112251 57100
187050 83100
112980 29377
157012 134211
135596 33147
85472 59785
139169 125631
153085 165140
82629 73365
25158 16327
191064 93990
123231 32916
130815 20323
129599 77035
144632 98686
67473 3578
172156 98862
21894 195995
16...

output:

199994

result:

ok single line: '199994'

Test #14:

score: 0
Accepted
time: 137ms
memory: 27772kb

input:

199999
37321 183353
197048 89193
114486 34848
82027 85518
62564 117961
17663 28259
91838 124561
188988 46866
156756 75225
105968 183481
118948 67500
75409 123761
107128 52670
171953 102720
62773 165219
194620 173567
31552 88489
97494 15048
189108 36762
11031 1741
64889 67129
158657 157875
191291 359...

output:

199994

result:

ok single line: '199994'

Test #15:

score: 0
Accepted
time: 121ms
memory: 27952kb

input:

200000
196903 77452
27188 55527
102207 165320
134712 55341
162994 81141
85731 30299
75243 18518
23639 84881
197033 143822
120492 51146
46281 145275
99830 195228
185002 53761
54098 31449
60141 191308
193012 177578
67355 11089
66265 166383
34969 194717
175543 128704
40124 39801
196897 185270
34468 798...

output:

5234

result:

ok single line: '5234'

Test #16:

score: 0
Accepted
time: 118ms
memory: 28252kb

input:

200000
164768 68803
153609 72233
28630 173584
188468 26064
147938 153547
106394 130342
153098 185806
157156 94496
141556 40929
79526 192838
66642 19962
39033 118375
82614 132264
116065 11968
2498 145405
27683 44830
188353 171809
40025 55356
95932 76953
71476 192804
36377 176226
150808 112053
62032 2...

output:

87285

result:

ok single line: '87285'

Test #17:

score: 0
Accepted
time: 128ms
memory: 27992kb

input:

200000
119064 87150
88474 101343
28775 181918
64539 128651
198006 125318
185007 906
160601 63351
80071 151133
7405 117288
156761 198069
31781 182812
115257 163727
194865 190486
132836 158527
96125 172835
18855 162329
765 9645
176621 71693
96969 35402
186625 109731
182338 109761
115810 163332
137380 ...

output:

195599

result:

ok single line: '195599'

Test #18:

score: 0
Accepted
time: 116ms
memory: 27884kb

input:

200000
169902 92723
183685 136214
82468 121180
30234 125829
158290 34267
142388 155698
94388 135816
148126 57444
85244 10951
62963 14036
58626 3752
79455 102202
159192 142432
135920 172208
126721 82167
142514 195323
156125 70347
82463 187407
112635 30481
140880 153276
102414 110060
38434 24494
24321...

output:

199958

result:

ok single line: '199958'

Test #19:

score: 0
Accepted
time: 128ms
memory: 27676kb

input:

200000
75340 12125
186658 150349
185083 75056
142561 56177
6639 88787
97721 128601
54847 130284
72089 41364
134594 85825
89026 1478
34173 162092
78486 25668
149033 80783
36585 139727
153979 90382
136059 69686
93621 131171
3723 142495
185400 122648
141853 112010
131142 128296
2182 75563
7646 66135
17...

output:

199983

result:

ok single line: '199983'

Test #20:

score: 0
Accepted
time: 129ms
memory: 27908kb

input:

200000
64437 16055
109346 72064
67189 162631
56772 2679
81291 80645
26361 105932
131328 121785
5385 124003
175691 190778
44906 12173
17800 9629
183834 114092
14088 114486
169877 22071
41393 117344
67569 89064
25109 113134
199399 42709
5100 127796
157865 96348
13852 117269
21494 40761
11254 184205
16...

output:

199995

result:

ok single line: '199995'

Test #21:

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

input:

200000
127523 42011
13665 102681
85434 22525
393 177456
110466 54815
51795 102134
10443 133958
29625 162496
124871 111891
63766 194601
93801 74135
76085 118306
73335 171042
21509 198993
5681 102827
169315 122442
110793 75074
57247 71260
167784 172752
35785 45521
1338 175685
109713 35872
102111 21849...

output:

199998

result:

ok single line: '199998'

Test #22:

score: 0
Accepted
time: 123ms
memory: 27932kb

input:

196419
49598 162509
7256 26430
144602 53005
152829 107595
151669 25597
57481 80612
187472 131966
95994 132915
130867 90111
180126 174293
66390 29521
165742 168338
193584 104911
119803 187301
75524 78858
67788 37052
181562 174827
118679 149133
1124 23095
132885 52723
128009 67344
168002 40276
117437 ...

output:

1

result:

ok single line: '1'

Test #23:

score: 0
Accepted
time: 4ms
memory: 14552kb

input:

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

output:

2

result:

ok single line: '2'

Test #24:

score: 0
Accepted
time: 4ms
memory: 15112kb

input:

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

output:

1

result:

ok single line: '1'

Test #25:

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

input:

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

output:

2

result:

ok single line: '2'

Test #26:

score: 0
Accepted
time: 2ms
memory: 14508kb

input:

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

output:

2

result:

ok single line: '2'

Test #27:

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

input:

22
8 19
6 4
5 16
18 16
4 8
7 11
5 12
5 15
9 15
2 17
22 14
10 2
9 1
1 13
11 13
15 19
3 20
9 10
13 20
22 11
21 10

output:

2

result:

ok single line: '2'

Test #28:

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

input:

22
15 18
5 9
12 2
21 8
7 19
21 10
3 20
11 7
10 1
22 2
19 22
2 20
3 5
19 16
1 22
20 13
12 14
10 18
17 4
6 13
17 21

output:

1

result:

ok single line: '1'

Test #29:

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

input:

22
3 22
1 22
16 1
9 12
13 16
4 3
15 13
12 19
17 11
15 21
14 2
13 8
22 2
18 6
10 21
3 18
7 8
16 9
5 17
9 20
5 15

output:

1

result:

ok single line: '1'

Test #30:

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

input:

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

output:

2

result:

ok single line: '2'

Test #31:

score: 0
Accepted
time: 2ms
memory: 14520kb

input:

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

output:

2

result:

ok single line: '2'

Test #32:

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

input:

90
56 36
28 17
84 5
61 38
46 37
88 1
47 17
8 1
78 8
31 65
48 69
40 32
43 14
44 36
5 27
25 42
64 11
7 13
4 67
30 15
23 76
18 72
85 80
26 22
51 53
26 90
70 23
52 19
5 55
31 6
42 16
83 69
77 57
38 84
50 60
3 30
74 50
54 6
11 63
14 84
39 72
88 55
35 38
7 11
2 27
15 82
59 20
14 23
8 64
75 87
56 10
76 81
...

output:

2

result:

ok single line: '2'

Test #33:

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

input:

6766
1527 2212
5434 1094
4049 914
3570 2232
2515 490
349 4841
3039 5766
2826 6391
5116 5101
3433 3944
6761 4999
1343 737
6660 5428
2259 625
497 6758
4729 133
1903 6608
3081 6070
2095 87
3684 3262
455 4275
6365 4646
4214 5192
897 2968
1716 4321
2682 2363
4186 3036
2468 2392
4930 2003
4667 6180
832 91...

output:

2

result:

ok single line: '2'

Test #34:

score: 0
Accepted
time: 130ms
memory: 28324kb

input:

200000
93236 67773
90060 162436
154117 85468
57878 134816
90874 148370
126714 129212
20272 124146
54874 71314
83805 71303
87020 10794
118298 68878
36796 169945
7163 39281
38439 15855
110414 22688
110178 77143
165371 165134
33268 60598
26710 83845
20383 21674
91283 129513
75876 128474
77150 108606
16...

output:

1377

result:

ok single line: '1377'

Test #35:

score: 0
Accepted
time: 4ms
memory: 14216kb

input:

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

output:

3

result:

ok single line: '3'

Test #36:

score: 0
Accepted
time: 4ms
memory: 14508kb

input:

15
13 14
5 3
9 2
2 14
10 15
13 1
12 1
12 5
11 2
4 13
4 10
14 7
8 12
6 10

output:

2

result:

ok single line: '2'

Test #37:

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

input:

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

output:

4

result:

ok single line: '4'

Test #38:

score: 0
Accepted
time: 2ms
memory: 14216kb

input:

17
11 4
7 17
5 12
12 10
1 7
4 10
17 14
1 10
16 2
16 8
16 7
3 17
9 3
15 9
14 6
9 13

output:

2

result:

ok single line: '2'

Test #39:

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

input:

20
5 4
3 14
9 1
16 2
20 12
6 11
7 11
4 10
8 18
7 13
2 5
8 3
20 6
1 5
6 19
15 17
17 4
9 3
9 11

output:

0

result:

ok single line: '0'

Test #40:

score: 0
Accepted
time: 4ms
memory: 14524kb

input:

31
14 31
23 2
1 22
10 13
3 4
9 8
10 17
29 30
7 11
25 18
12 9
17 11
22 4
3 14
28 15
30 20
20 4
18 6
24 3
16 5
17 2
13 15
26 27
25 12
24 19
1 10
23 21
23 26
22 25
12 16

output:

5

result:

ok single line: '5'

Test #41:

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

input:

32
27 15
19 20
3 2
15 11
28 20
15 9
14 31
32 23
27 14
5 12
21 16
29 5
21 22
8 31
16 17
4 14
28 26
18 27
3 25
4 1
22 3
2 32
13 7
5 4
17 24
2 10
1 22
6 28
21 6
30 6
31 7

output:

6

result:

ok single line: '6'

Test #42:

score: 0
Accepted
time: 4ms
memory: 14292kb

input:

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

output:

0

result:

ok single line: '0'

Test #43:

score: 0
Accepted
time: 4ms
memory: 14548kb

input:

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

output:

0

result:

ok single line: '0'

Test #44:

score: 0
Accepted
time: 4ms
memory: 14596kb

input:

193
92 52
55 130
26 177
87 150
110 164
123 43
116 143
192 96
13 53
25 40
91 85
156 30
106 115
149 20
9 134
176 83
153 52
135 175
65 35
43 187
52 131
41 40
9 113
41 181
105 89
69 28
183 166
74 147
130 20
170 124
15 1
26 80
137 37
95 102
177 114
167 27
54 94
25 60
50 135
101 167
14 171
104 3
143 185
3...

output:

26

result:

ok single line: '26'

Test #45:

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

input:

200000
148698 67370
39179 145959
175045 19072
135937 89662
191620 198262
56418 28034
182226 156798
192485 171736
188580 132838
159930 113812
126124 64033
81424 136512
65714 163849
89717 16599
1241 64761
66537 36129
141953 31476
180966 187111
90997 17899
184926 24597
48220 69679
187441 83459
77833 10...

output:

1384

result:

ok single line: '1384'

Test #46:

score: 0
Accepted
time: 139ms
memory: 27788kb

input:

200000
889 167990
179247 195474
70620 170546
110296 167511
134544 170629
66024 86183
89963 98909
117448 96819
166282 195044
42691 181105
150270 183563
117908 158186
88558 120976
54239 119740
94935 193205
129002 41428
165608 114467
72317 30441
198684 109854
462 72431
65444 77653
50168 9221
132141 115...

output:

199995

result:

ok single line: '199995'

Test #47:

score: 0
Accepted
time: 141ms
memory: 27884kb

input:

200000
76756 19493
112168 107128
53133 62242
70939 186078
81801 45256
21435 80902
132044 5782
7191 70507
86432 139322
185817 176965
163412 8586
112875 100950
91127 48700
127289 108361
15980 31952
30716 107645
9453 62853
144313 9895
148167 83633
98389 158321
58381 145434
163409 5819
74955 179524
1223...

output:

199995

result:

ok single line: '199995'

Test #48:

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

input:

99
52 37
36 13
36 29
60 3
92 46
6 80
98 44
65 63
83 73
77 72
16 31
93 45
46 20
87 22
82 95
3 71
11 92
28 21
60 24
94 37
69 15
89 93
56 95
35 74
43 20
51 16
32 39
65 41
21 84
46 7
76 12
82 96
75 68
18 75
15 82
19 35
51 85
20 78
30 67
86 44
51 11
29 93
79 41
97 52
72 2
83 95
5 70
27 28
22 94
94 34
28 ...

output:

94

result:

ok single line: '94'

Test #49:

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

input:

999
759 604
844 700
914 79
487 236
37 53
548 780
7 463
881 891
119 283
220 176
800 575
824 779
549 250
794 616
80 734
854 193
730 793
241 355
16 443
542 897
704 567
113 651
421 527
407 585
85 958
668 497
716 317
708 8
777 721
690 23
493 238
569 444
852 462
561 966
82 940
379 722
627 347
779 908
812 ...

output:

994

result:

ok single line: '994'

Test #50:

score: 0
Accepted
time: 115ms
memory: 27968kb

input:

200000
71762 128178
159376 135935
149966 97854
124447 12126
47646 92277
148888 98881
198840 151210
178412 105674
170040 82589
3719 37528
132834 6724
156840 23561
31996 83407
88709 103602
86792 16998
102784 9600
41549 53148
741 13491
70940 50722
131598 195062
34691 172029
37034 182904
56619 142301
42...

output:

197731

result:

ok single line: '197731'

Test #51:

score: 0
Accepted
time: 113ms
memory: 28000kb

input:

200000
35455 178406
63055 57212
86875 14887
113693 125870
166519 73828
21890 89564
144962 55564
39502 7468
77466 140775
89459 55713
97963 24040
179441 66830
77724 11961
188838 47282
167148 90674
79640 155335
66333 27976
51896 100957
57370 83089
144287 150099
123814 146896
117004 196837
60273 99891
1...

output:

197665

result:

ok single line: '197665'

Test #52:

score: 0
Accepted
time: 114ms
memory: 28128kb

input:

200000
165358 9319
31871 37246
178292 93703
190872 132194
167892 96889
85352 77738
126655 137653
29785 154161
50977 138984
18165 94676
132457 95872
20548 175478
21795 167145
179895 103462
16732 143125
29718 320
4967 65939
80255 34661
19125 90507
51130 149398
23957 131041
188783 179442
198771 60049
1...

output:

197706

result:

ok single line: '197706'

Test #53:

score: 0
Accepted
time: 118ms
memory: 27956kb

input:

200000
96044 50673
175479 160492
122472 17370
108467 173774
15658 180449
108378 75307
72626 90638
18578 121477
144343 12761
193892 6514
4763 187018
28821 60686
64364 178057
137027 186724
163414 184183
21132 75564
80030 180007
6819 58563
139858 102431
49514 14870
194725 186419
54697 76168
178418 6614...

output:

197667

result:

ok single line: '197667'

Test #54:

score: 0
Accepted
time: 4ms
memory: 14608kb

input:

4
1 2
4 2
1 3

output:

0

result:

ok single line: '0'

Test #55:

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

input:

5
2 1
1 4
3 2
5 3

output:

1

result:

ok single line: '1'

Test #56:

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

input:

6
3 1
3 4
1 2
3 5
6 2

output:

0

result:

ok single line: '0'

Test #57:

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

input:

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

output:

2

result:

ok single line: '2'

Test #58:

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

input:

8
3 2
7 2
2 1
6 4
8 6
1 5
5 4

output:

2

result:

ok single line: '2'

Test #59:

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

input:

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

output:

1

result:

ok single line: '1'

Test #60:

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

input:

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

output:

4

result:

ok single line: '4'

Test #61:

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

input:

15
1 15
10 2
1 7
9 13
7 11
5 3
9 11
3 4
5 2
11 12
14 8
4 15
4 14
6 5

output:

10

result:

ok single line: '10'

Test #62:

score: 0
Accepted
time: 4ms
memory: 14540kb

input:

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

output:

4

result:

ok single line: '4'

Test #63:

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

input:

17
14 17
11 4
9 3
1 16
8 14
6 15
12 16
2 4
9 16
10 14
17 1
3 7
17 6
13 6
5 12
15 4

output:

3

result:

ok single line: '3'

Test #64:

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

input:

20
14 18
8 7
11 8
20 15
4 20
18 2
17 6
13 3
12 5
3 14
11 10
5 9
1 7
7 4
19 12
8 14
1 12
3 16
17 4

output:

3

result:

ok single line: '3'

Test #65:

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

input:

31
4 14
23 18
24 8
9 15
24 27
11 3
26 4
30 1
5 31
10 6
28 27
13 16
28 22
19 28
5 25
7 30
25 29
9 1
6 11
21 12
16 8
22 25
24 4
20 27
11 16
8 17
23 20
15 12
9 2
30 22

output:

21

result:

ok single line: '21'

Test #66:

score: 0
Accepted
time: 4ms
memory: 14284kb

input:

32
3 19
21 27
16 6
13 31
26 27
11 9
31 8
23 27
22 7
30 5
21 14
28 6
15 25
20 18
22 24
18 5
21 1
31 18
26 20
16 5
11 14
10 20
4 25
26 12
9 3
3 17
4 2
29 22
32 19
25 1
9 7

output:

19

result:

ok single line: '19'

Test #67:

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

input:

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

output:

2

result:

ok single line: '2'

Test #68:

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

input:

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

output:

6

result:

ok single line: '6'

Test #69:

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

input:

1102
546 259
837 314
749 847
642 908
1051 375
547 8
114 1063
782 601
1040 448
200 929
1073 365
525 174
430 130
93 425
771 169
21 561
1060 375
1066 107
162 211
647 662
196 100
481 1092
786 740
296 392
755 997
431 542
6 876
93 907
4 11
487 80
54 206
303 868
917 903
471 867
45 963
239 642
687 28
91 53
...

output:

959

result:

ok single line: '959'

Test #70:

score: 0
Accepted
time: 7ms
memory: 16204kb

input:

29485
1686 8384
2457 458
19832 12581
13421 11479
28634 3472
18300 7871
15712 19408
22775 25985
21929 24016
27301 7399
12982 23315
17523 16265
19291 27179
12733 18267
4091 6137
28444 9014
10887 21137
8812 10366
25079 1099
16901 12246
22543 139
9210 16958
12203 26663
28740 29176
3506 3728
27885 3490
7...

output:

28445

result:

ok single line: '28445'

Test #71:

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

input:

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

output:

5

result:

ok single line: '5'

Test #72:

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

input:

15
9 11
15 2
4 6
14 6
12 7
14 7
1 6
14 3
15 8
10 11
2 5
4 13
2 1
4 11

output:

0

result:

ok single line: '0'

Test #73:

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

input:

20
19 11
13 16
2 9
1 5
14 12
14 18
10 16
4 1
14 6
15 6
20 3
17 18
8 5
20 19
7 17
10 2
3 15
13 15
5 18

output:

15

result:

ok single line: '15'

Test #74:

score: 0
Accepted
time: 2ms
memory: 15032kb

input:

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

output:

45

result:

ok single line: '45'

Test #75:

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

input:

100
75 59
70 18
69 7
55 79
70 100
34 100
53 18
16 3
21 2
74 84
74 6
7 36
54 62
22 45
28 32
68 2
27 32
14 96
3 60
85 48
97 94
78 4
87 12
72 99
47 23
49 86
62 10
60 61
73 96
60 94
5 89
14 24
24 46
35 64
86 20
38 18
40 27
68 48
45 67
58 55
74 93
44 59
100 11
43 46
59 81
91 13
41 40
15 82
91 33
92 25
87...

output:

98

result:

ok single line: '98'

Test #76:

score: 0
Accepted
time: 2ms
memory: 14180kb

input:

100
22 21
3 84
95 62
99 33
8 5
54 14
6 85
33 89
59 76
35 47
24 92
67 23
57 39
72 10
29 47
11 98
73 86
30 99
41 26
68 80
56 71
88 69
27 45
69 66
19 80
99 31
74 54
96 19
43 3
7 67
97 63
62 36
77 39
56 52
25 14
38 46
6 58
37 13
64 7
95 78
79 41
65 38
72 64
46 42
41 94
13 77
8 82
59 29
92 69
6 2
17 79
9...

output:

95

result:

ok single line: '95'

Test #77:

score: 0
Accepted
time: 4ms
memory: 14832kb

input:

100
9 14
39 20
85 64
17 63
90 32
8 51
15 19
89 52
51 43
2 81
29 80
35 22
86 72
21 18
77 67
96 66
4 30
62 96
3 73
45 74
83 1
26 28
16 20
53 92
82 7
44 14
48 2
92 41
31 59
9 95
98 19
95 57
12 91
99 86
66 42
13 18
68 29
87 49
97 93
79 16
96 100
3 68
48 38
27 45
53 37
6 1
57 78
37 33
10 55
17 73
15 69
4...

output:

95

result:

ok single line: '95'

Test #78:

score: 0
Accepted
time: 4ms
memory: 14232kb

input:

100
47 23
10 52
48 90
67 94
15 41
72 54
86 66
46 65
53 89
92 89
80 15
5 65
88 75
21 18
35 56
28 1
28 69
66 60
42 94
85 21
97 54
57 1
20 9
28 93
60 92
47 93
50 73
83 50
18 72
24 13
52 55
56 85
56 99
15 27
38 86
3 44
4 87
55 71
30 80
88 29
18 59
53 42
87 44
3 81
82 91
68 58
95 30
42 9
22 62
66 51
100 ...

output:

86

result:

ok single line: '86'

Test #79:

score: 0
Accepted
time: 132ms
memory: 28064kb

input:

200000
100998 174087
158540 122779
168545 195470
86682 13242
151578 81990
41426 180930
52764 151840
146840 166657
153661 183772
184324 23777
28034 146447
153943 151157
7844 16228
50251 12511
11 121112
75760 173262
167702 64341
77869 193778
145611 192118
190325 8899
27916 15792
51751 75376
45412 6193...

output:

0

result:

ok single line: '0'

Test #80:

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

input:

200000
168887 99558
126198 177075
181007 73079
108341 170114
123043 82403
164356 148614
56554 111669
82831 139806
150604 168090
40871 120525
49216 197395
89268 146656
133415 92094
100299 82067
138956 107941
9190 167575
152940 46848
55315 5793
96372 74604
92069 179869
119485 61213
61580 131656
104281...

output:

0

result:

ok single line: '0'

Test #81:

score: 0
Accepted
time: 129ms
memory: 28188kb

input:

200000
66182 136392
76817 100486
80500 137701
19180 20777
166786 47759
76360 134439
28835 193802
86671 166625
80338 94843
132411 126305
4617 156217
80837 114403
199244 92697
58429 104099
175001 102745
50762 188648
131268 5172
25825 18715
52188 80195
155363 180626
84734 19878
124035 181829
44536 3583...

output:

25

result:

ok single line: '25'

Test #82:

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

input:

15
9 13
3 11
8 6
11 2
14 8
10 6
15 4
4 5
10 9
14 7
1 3
6 12
1 14
3 4

output:

4

result:

ok single line: '4'

Test #83:

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

input:

148
11 102
6 49
28 87
98 104
56 106
20 9
47 83
92 47
11 20
138 96
129 102
53 138
46 106
52 141
4 10
8 10
48 97
43 132
75 13
26 18
37 58
148 103
110 136
88 84
50 118
127 105
59 148
139 111
147 38
22 17
58 116
77 13
34 74
116 68
137 63
1 16
33 85
25 5
125 76
142 110
28 83
35 56
111 105
12 77
73 24
63 ...

output:

50

result:

ok single line: '50'

Test #84:

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

input:

1023
914 569
859 981
974 959
130 713
311 393
305 500
1016 704
310 766
904 89
362 240
180 112
871 863
930 1008
800 743
574 933
273 279
1017 398
18 740
285 191
805 710
598 56
968 512
533 8
571 786
985 426
771 617
378 440
499 241
821 819
823 470
851 345
799 616
198 90
328 65
299 958
472 366
519 510
870...

output:

0

result:

ok single line: '0'

Test #85:

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

input:

1024
925 237
441 496
988 672
839 159
371 534
611 26
831 80
274 751
816 214
645 130
413 776
16 940
757 912
837 351
577 33
397 255
847 726
849 130
119 577
973 659
160 108
575 860
578 629
318 369
806 925
829 767
578 772
355 878
450 514
370 562
116 146
112 712
425 291
761 278
526 848
671 986
466 936
989...

output:

3

result:

ok single line: '3'