sysy/hidden_functional_c/input/13_LCA.in

1000 1000
1 2
1 3
2 4
3 5
1 6
4 7
7 8
7 9
4 10
4 11
8 12
11 13
5 14
13 15
3 16
15 17
2 18
1 19
10 20
14 21
14 22
21 23
1 24
23 25
22 26
14 27
8 28
7 29
28 30
21 31
15 32
13 33
9 34
26 35
20 36
14 37
32 38
28 39
5 40
5 41
3 42
33 43
20 44
15 45
43 46
36 47
22 48
22 49
22 50
19 51
32 52
24 53
36 54
53 55
27 56
37 57
2 58
30 59
45 60
17 61
32 62
4 63
33 64
28 65
14 66
19 67
5 68
34 69
37 70
43 71
18 72
1 73
53 74
67 75
26 76
47 77
49 78
8 79
23 80
33 81
23 82
37 83
68 84
81 85
28 86
10 87
74 88
55 89
81 90
8 91
8 92
77 93
92 94
21 95
60 96
74 97
69 98
41 99
8 100
47 101
21 102
89 103
70 104
17 105
65 106
84 107
24 108
56 109
99 110
55 111
29 112
106 113
113 114
86 115
4 116
106 117
53 118
81 119
2 120
32 121
29 122
9 123
29 124
52 125
92 126
67 127
47 128
111 129
93 130
11 131
117 132
6 133
29 134
90 135
18 136
86 137
38 138
109 139
115 140
77 141
137 142
57 143
58 144
107 145
65 146
124 147
134 148
80 149
128 150
91 151
24 152
115 153
16 154
40 155
35 156
120 157
79 158
33 159
29 160
96 161
150 162
139 163
118 164
108 165
76 166
47 167
70 168
154 169
64 170
153 171
110 172
161 173
16 174
157 175
18 176
72 177
129 178
125 179
29 180
23 181
28 182
141 183
150 184
6 185
152 186
25 187
105 188
169 189
185 190
139 191
188 192
176 193
140 194
17 195
147 196
170 197
12 198
149 199
98 200
149 201
37 202
198 203
19 204
24 205
37 206
193 207
125 208
208 209
153 210
20 211
180 212
172 213
81 214
53 215
196 216
173 217
159 218
56 219
214 220
33 221
117 222
133 223
134 224
196 225
100 226
112 227
163 228
155 229
114 230
69 231
145 232
183 233
209 234
155 235
67 236
143 237
4 238
30 239
191 240
202 241
94 242
86 243
8 244
57 245
242 246
32 247
5 248
158 249
207 250
230 251
122 252
118 253
174 254
224 255
55 256
230 257
118 258
55 259
123 260
47 261
128 262
250 263
57 264
72 265
199 266
102 267
111 268
113 269
88 270
14 271
155 272
10 273
11 274
255 275
45 276
220 277
216 278
236 279
102 280
11 281
266 282
121 283
98 284
183 285
246 286
125 287
51 288
6 289
257 290
232 291
274 292
24 293
46 294
172 295
93 296
141 297
241 298
278 299
131 300
42 301
153 302
258 303
285 304
184 305
235 306
137 307
254 308
225 309
297 310
178 311
168 312
265 313
20 314
17 315
223 316
177 317
88 318
6 319
150 320
169 321
250 322
312 323
148 324
130 325
34 326
127 327
261 328
54 329
19 330
218 331
127 332
201 333
207 334
75 335
215 336
131 337
251 338
46 339
248 340
57 341
191 342
52 343
175 344
342 345
336 346
331 347
255 348
259 349
33 350
226 351
223 352
329 353
166 354
333 355
169 356
241 357
36 358
51 359
1 360
341 361
31 362
322 363
102 364
291 365
195 366
282 367
30 368
234 369
98 370
296 371
89 372
46 373
368 374
311 375
261 376
180 377
79 378
217 379
346 380
265 381
262 382
289 383
30 384
384 385
74 386
321 387
246 388
192 389
314 390
308 391
262 392
225 393
358 394
232 395
254 396
121 397
191 398
48 399
94 400
367 401
18 402
34 403
232 404
319 405
256 406
233 407
103 408
378 409
213 410
376 411
119 412
2 413
404 414
174 415
236 416
79 417
355 418
198 419
327 420
275 421
198 422
405 423
201 424
82 425
86 426
4 427
31 428
42 429
147 430
266 431
85 432
191 433
20 434
110 435
369 436
360 437
65 438
137 439
230 440
52 441
212 442
21 443
206 444
250 445
362 446
83 447
320 448
308 449
51 450
64 451
162 452
285 453
94 454
135 455
230 456
230 457
429 458
274 459
245 460
243 461
107 462
154 463
148 464
157 465
288 466
214 467
281 468
205 469
348 470
222 471
80 472
458 473
164 474
461 475
221 476
84 477
351 478
383 479
248 480
465 481
20 482
177 483
340 484
223 485
376 486
119 487
408 488
71 489
425 490
421 491
288 492
96 493
101 494
351 495
462 496
361 497
237 498
275 499
36 500
328 501
117 502
10 503
138 504
29 505
74 506
485 507
416 508
285 509
81 510
489 511
426 512
270 513
48 514
232 515
499 516
91 517
323 518
77 519
152 520
166 521
156 522
457 523
158 524
283 525
347 526
335 527
243 528
388 529
519 530
93 531
239 532
394 533
246 534
71 535
532 536
170 537
349 538
269 539
413 540
151 541
464 542
183 543
502 544
89 545
153 546
211 547
385 548
352 549
192 550
229 551
58 552
42 553
269 554
325 555
405 556
99 557
296 558
429 559
432 560
526 561
60 562
281 563
87 564
200 565
169 566
50 567
163 568
92 569
528 570
501 571
516 572
459 573
526 574
45 575
7 576
480 577
210 578
51 579
532 580
248 581
533 582
231 583
338 584
417 585
558 586
241 587
144 588
553 589
400 590
348 591
120 592
345 593
333 594
325 595
193 596
83 597
68 598
100 599
241 600
217 601
192 602
284 603
39 604
378 605
294 606
302 607
475 608
23 609
344 610
591 611
509 612
218 613
493 614
540 615
176 616
443 617
410 618
564 619
228 620
390 621
508 622
155 623
483 624
283 625
98 626
539 627
272 628
502 629
16 630
489 631
477 632
38 633
428 634
524 635
8 636
569 637
179 638
22 639
28 640
501 641
393 642
140 643
238 644
184 645
597 646
104 647
293 648
240 649
213 650
303 651
372 652
87 653
500 654
22 655
555 656
118 657
55 658
276 659
417 660
41 661
478 662
84 663
661 664
69 665
554 666
471 667
402 668
565 669
438 670
272 671
117 672
564 673
155 674
371 675
535 676
52 677
127 678
329 679
358 680
82 681
363 682
567 683
594 684
341 685
32 686
120 687
414 688
97 689
665 690
211 691
290 692
72 693
549 694
131 695
237 696
388 697
333 698
413 699
317 700
15 701
285 702
510 703
32 704
702 705
559 706
246 707
373 708
285 709
307 710
234 711
96 712
64 713
515 714
125 715
256 716
310 717
309 718
245 719
467 720
609 721
643 722
386 723
503 724
571 725
549 726
110 727
270 728
457 729
162 730
401 731
670 732
91 733
285 734
236 735
396 736
507 737
554 738
535 739
332 740
163 741
465 742
530 743
513 744
707 745
167 746
554 747
262 748
327 749
371 750
702 751
101 752
223 753
498 754
47 755
216 756
367 757
592 758
263 759
39 760
125 761
556 762
3 763
501 764
43 765
520 766
500 767
214 768
118 769
393 770
553 771
226 772
299 773
738 774
192 775
279 776
177 777
385 778
388 779
265 780
411 781
495 782
436 783
41 784
646 785
520 786
285 787
760 788
637 789
540 790
538 791
460 792
402 793
365 794
593 795
74 796
533 797
672 798
699 799
591 800
215 801
456 802
400 803
44 804
385 805
544 806
133 807
393 808
318 809
395 810
602 811
641 812
685 813
608 814
744 815
266 816
149 817
449 818
280 819
305 820
407 821
41 822
248 823
336 824
329 825
349 826
333 827
138 828
337 829
475 830
264 831
397 832
350 833
9 834
685 835
739 836
156 837
770 838
602 839
276 840
74 841
678 842
282 843
831 844
695 845
620 846
329 847
575 848
642 849
649 850
690 851
517 852
297 853
593 854
553 855
789 856
350 857
202 858
399 859
518 860
740 861
714 862
234 863
284 864
194 865
275 866
678 867
180 868
224 869
195 870
809 871
12 872
309 873
75 874
89 875
779 876
122 877
129 878
753 879
677 880
781 881
802 882
877 883
241 884
562 885
608 886
536 887
838 888
15 889
448 890
28 891
112 892
765 893
215 894
333 895
733 896
468 897
712 898
873 899
695 900
183 901
520 902
361 903
239 904
823 905
188 906
175 907
511 908
788 909
202 910
420 911
341 912
166 913
595 914
117 915
610 916
147 917
897 918
115 919
464 920
790 921
465 922
903 923
109 924
266 925
4 926
74 927
925 928
40 929
106 930
255 931
767 932
910 933
358 934
151 935
856 936
578 937
828 938
122 939
538 940
455 941
508 942
725 943
645 944
401 945
642 946
350 947
86 948
443 949
820 950
70 951
691 952
121 953
382 954
809 955
65 956
718 957
300 958
798 959
72 960
219 961
170 962
443 963
373 964
836 965
689 966
701 967
420 968
513 969
403 970
49 971
169 972
201 973
938 974
610 975
110 976
60 977
869 978
428 979
664 980
672 981
69 982
387 983
376 984
184 985
876 986
613 987
482 988
81 989
369 990
149 991
875 992
181 993
361 994
518 995
474 996
531 997
728 998
407 999
804 1000
635 543
387 141
166 478
97 72
67 116
699 998
610 281
728 682
566 850
503 288
416 663
779 245
359 707
481 714
951 731
273 175
667 585
414 11
82 184
651 862
859 500
780 349
30 820
670 859
498 595
609 524
768 266
972 387
101 126
208 453
627 51
635 832
843 646
181 401
262 276
776 832
180 121
292 907
766 562
156 961
836 263
528 765
503 604
81 500
952 603
653 289
472 930
927 640
40 314
590 460
291 653
773 717
623 822
383 65
377 740
3 891
7 213
168 882
733 509
464 600
240 36
318 116
107 712
25 596
55 498
503 966
682 345
519 627
43 657
396 901
791 420
984 398
632 149
658 503
102 716
752 121
588 342
53 421
16 47
896 429
747 71
415 398
25 428
436 285
186 67
838 832
581 328
477 173
675 212
928 486
958 129
822 31
451 897
295 874
654 466
536 543
940 400
180 303
587 316
735 615
798 124
804 572
97 379
942 632
117 771
251 221
251 426
674 72
297 53
519 969
511 951
702 406
60 802
118 233
200 999
122 852
775 997
375 277
908 871
994 317
537 376
801 244
316 140
192 827
795 964
914 62
820 657
458 968
200 879
877 927
130 751
748 351
627 905
127 474
142 535
262 472
716 31
522 63
241 383
698 713
127 35
43 612
931 946
824 500
427 482
233 53
755 908
164 332
157 381
267 291
762 299
681 529
943 829
563 202
914 183
569 261
224 40
337 611
462 154
987 161
565 240
148 571
254 319
51 311
601 411
709 318
198 715
895 389
590 492
674 458
718 855
247 594
204 293
798 583
95 17
257 784
707 11
329 404
714 960
370 732
401 667
733 430
818 598
441 627
84 759
966 114
59 153
797 564
146 614
630 594
730 593
955 886
289 436
395 284
367 355
21 765
194 767
364 105
731 364
474 156
621 167
319 439
2 679
292 468
61 500
444 273
159 790
225 398
33 799
505 972
736 399
165 877
981 281
996 880
35 712
878 822
612 655
685 548
15 614
465 328
601 428
217 260
9 111
909 794
765 42
792 766
642 852
484 309
540 623
334 480
301 927
933 563
462 912
877 618
297 829
256 693
304 897
359 472
265 313
706 620
385 381
232 849
157 26
648 68
547 49
975 333
247 199
462 259
228 709
537 691
735 525
773 792
615 39
703 132
751 232
612 760
608 135
512 196
263 117
165 160
844 161
711 491
101 91
799 172
214 329
205 687
478 301
691 329
460 444
675 393
504 562
48 287
834 111
579 560
71 96
256 95
585 914
4 966
489 38
718 154
840 55
355 274
602 669
465 45
789 414
975 139
777 292
754 375
934 610
705 333
427 4
269 312
277 364
401 625
778 118
172 470
743 970
990 526
570 344
757 454
945 710
1 84
810 721
331 106
438 743
98 35
699 217
580 718
342 975
92 332
801 472
793 263
140 543
238 782
588 61
770 347
782 532
252 122
228 591
685 934
321 665
881 134
851 19
993 812
143 193
16 437
51 295
189 808
589 191
251 427
125 528
59 373
494 906
496 663
596 73
738 532
665 916
286 970
134 867
411 279
67 628
923 426
233 117
659 463
889 174
701 262
986 13
270 112
774 479
552 117
648 721
989 641
962 664
531 274
904 95
75 941
367 970
439 349
811 951
124 449
62 700
64 177
288 47
526 686
802 413
485 429
421 802
465 473
747 382
829 995
288 2
972 255
603 6
956 762
562 413
464 432
608 624
670 880
565 247
11 195
975 718
519 495
968 395
129 336
682 66
67 957
211 969
974 390
503 165
577 282
713 65
688 41
920 672
270 357
904 836
553 280
774 878
273 424
759 93
510 753
61 792
113 929
318 623
787 438
719 821
237 363
403 783
454 924
280 674
509 723
354 183
413 414
189 480
572 37
789 299
90 434
362 849
471 202
640 31
203 257
971 710
493 439
362 726
399 298
21 994
176 260
25 374
853 940
976 213
511 777
210 116
964 600
154 923
953 786
394 793
854 156
594 365
442 346
644 308
301 840
451 16
741 828
768 475
39 946
722 743
211 549
501 283
557 174
312 654
798 509
16 57
773 651
997 610
917 214
406 992
7 217
44 856
683 747
44 163
258 721
622 765
399 468
993 122
127 307
816 656
713 924
926 831
792 485
699 274
265 60
276 104
959 623
722 672
186 993
66 765
882 443
910 687
808 632
939 255
910 286
561 754
936 622
107 486
760 80
139 157
260 376
999 767
438 570
563 720
836 975
418 628
666 717
349 679
933 825
110 287
392 843
816 670
507 327
406 274
430 266
994 545
663 689
611 344
63 452
426 525
504 898
967 843
874 169
993 315
601 806
1000 454
123 992
670 816
89 629
247 428
324 519
559 592
935 986
437 169
693 349
598 862
57 548
716 564
878 930
735 60
513 830
173 87
902 987
968 843
622 342
212 214
157 945
930 123
643 91
439 718
579 688
235 36
952 635
564 951
10 829
11 651
737 875
861 183
377 990
683 828
393 998
294 895
369 549
639 575
292 11
698 77
465 871
857 933
883 416
596 773
775 244
118 958
141 511
852 979
806 869
867 534
780 199
747 512
87 148
159 738
166 378
600 856
788 630
397 809
933 22
618 345
302 707
217 735
713 794
663 420
953 871
421 881
392 85
232 519
256 478
208 742
950 774
755 159
967 737
111 152
848 251
957 728
814 149
943 525
944 879
749 605
485 249
333 521
39 228
58 564
658 647
420 617
775 607
695 174
677 94
344 805
884 524
25 301
825 698
576 967
923 121
369 676
196 759
338 701
616 586
584 395
11 273
879 355
881 138
231 574
378 557
433 926
226 614
311 457
775 403
523 238
265 49
159 891
591 460
397 496
891 206
831 333
687 253
390 709
282 567
476 620
898 12
625 260
68 123
877 287
876 194
242 751
641 140
599 400
895 583
141 347
31 137
390 971
31 718
636 131
751 313
324 463
74 1000
122 300
938 141
334 351
101 813
952 575
326 94
28 902
248 573
61 520
842 279
348 802
933 873
185 335
150 35
34 860
511 223
364 507
857 448
260 697
624 310
755 211
112 301
873 134
654 711
341 934
735 847
719 688
375 19
53 255
466 524
746 86
593 328
775 109
158 801
462 34
596 781
81 216
702 707
418 306
591 707
553 110
150 677
696 624
230 524
47 748
186 48
375 792
253 130
930 150
535 410
542 744
311 131
837 974
279 12
718 606
68 869
546 623
246 217
740 593
340 827
874 138
281 877
6 601
750 533
294 288
31 636
766 187
161 341
353 955
912 791
12 422
44 979
195 909
501 641
468 286
423 192
69 693
293 704
588 74
361 394
30 234
420 391
84 795
101 580
723 436
209 13
343 734
642 253
893 890
175 142
333 360
405 598
653 401
827 697
91 592
825 187
930 120
266 597
176 13
800 719
731 250
983 8
612 425
314 624
765 505
216 489
438 450
202 620
669 442
33 28
567 759
230 210
806 496
860 847
565 333
583 11
18 647
72 565
541 982
486 385
225 305
106 53
673 14
455 308
335 693
803 840
49 901
748 32
230 206
538 607
617 147
793 472
37 987
968 216
953 577
233 805
857 177
543 339
646 881
573 997
836 980
233 375
758 236
441 980
587 988
486 331
802 555
893 278
846 190
766 212
16 798
326 351
689 225
105 868
217 686
17 30
404 52
640 249
581 514
853 432
762 519
73 338
967 916
105 318
529 812
609 223
573 897
473 287
154 613
298 929
958 370
774 666
267 714
227 413
196 847
365 431
768 958
873 789
458 734
546 977
199 339
587 506
792 123
735 59
987 298
19 384
50 945
10 792
556 668
514 588
18 752
61 230
370 785
518 285
613 828
518 415
273 164
286 104
162 64
713 21
756 500
796 732
523 157
824 805
392 431
534 689
270 409
545 594
878 640
819 415
829 490
653 336
439 101
517 291
311 952
451 229
960 418
575 247
403 835
265 750
439 795
555 798
743 708
699 100
514 620
461 517
204 694
147 466
756 642
945 15
595 418
835 748
346 555
741 761
511 748
542 357
506 949
8 449
548 248
219 707
223 413
458 679
496 427
420 956
970 251
20 717
464 565
471 855
967 809
908 563
919 477
777 802
250 424
671 785
843 149
913 241
271 417
195 722
678 767
369 967
683 999
915 389
595 498
658 385
947 561
390 565
366 217
640 166
302 615
115 662
254 496
913 27
749 525
643 107
73 426
776 11
399 107
604 691
427 345
906 613
178 726
942 647
812 895
862 934
947 466
313 976
3 201
725 225
684 103
880 719
729 108
215 655
345 480
824 170
783 124
849 81
727 312
206 790
723 891
708 67
395 22
222 20
597 397
851 298
16 280
739 730
736 96
575 953
475 81
204 751
183 609
920 404
193 262
504 477
896 268
289 563
582 290
38 862
159 530
161 888
969 526
621 900
204 704
136 548
298 678
286 691
94 832
93 557
386 639
906 596
158 281
922 546
407 92
973 311
550 917
442 134
33 518
573 414
961 236
914 709
399 610
442 551
460 845
483 534
482 197
477 740
285 991
434 750
60 43
959 407
892 961
478 752