CT30419

Last canals of Bhavi

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

At the mushroom groves of Fungaldeep, Bhavi records each canals in a worn leather ledger. The guild wants answers, not guesses. Task: Print the minimum number of edges on a path from s to t, or -1. Input format: First line: n m s t. Next m lines: u v. Output format: Print the BFS distance or -1. Constraints: 1 <= n <= 1435; 0 <= m <= 2870.

Example 1:

Input: 1392 2609 1 1392 753 1056 799 1053 153 660 1190 1268 1384 1387 1284 1308 239 271 1038 1281 722 1238 509 786 1073 1387 202 581 477 1388 146 282 787 1312 177 331 77 1092 19 1334 85 329 192 258 513 1335 188 901 637 751 723 1205 1020 1327 447 753 20 146 42 90 93 420 32 531 717 1282 394 1115 78 144 215 345 830 882 168 391 69 1268 244 498 928 1359 1050 1136 872 951 1158 1202 244 456 341 1037 1150 1267 308 493 693 1023 1013 1312 173 230 605 618 365 1277 311 396 211 643 210 935 389 513 231 1365 338 698 109 692 723 865 725 1004 207 1137 602 630 512 1103 38 804 70 1381 1266 1380 152 848 131 640 528 819 332 765 335 616 105 635 298 1025 713 1158 63 210 704 1227 549 930 547 605 42 933 741 1295 195 1242 235 495 987 1179 474 1147 42 665 855 1254 322 621 291 541 482 823 684 1163 560 1177 515 917 9 1327 370 769 616 1387 487 757 1284 1337 292 1059 1314 1324 132 450 691 792 24 259 138 247 356 714 581 915 769 1385 672 943 267 1199 435 1162 94 261 460 1297 285 861 237 949 364 1110 244 360 191 1126 311 399 23 150 531 957 576 783 633 915 568 613 15 261 270 1102 74 940 679 729 367 1043 35 686 673 1218 23 981 787 990 278 873 1159 1275 220 813 520 1314 316 436 307 497 378 1031 144 914 450 1186 195 1298 603 612 422 1067 236 1038 456 608 1111 1180 1002 1152 259 988 114 141 338 1170 306 1144 270 527 302 1067 24 281 786 1172 628 1093 81 316 526 696 648 746 756 913 254 1276 745 874 296 459 292 637 142 809 342 1183 485 697 392 509 150 472 1075 1196 746 1136 306 1283 118 227 230 343 311 897 305 705 523 726 406 634 179 1277 238 1229 974 975 257 575 642 876 536 918 88 527 329 422 763 850 183 1072 460 1241 244 328 1232 1334 498 1341 581 1020 148 1267 421 812 796 907 569 1108 233 336 440 815 838 1304 1159 1281 160 1242 73 1211 120 766 569 766 607 751 868 1260 334 968 558 1016 42 1234 281 700 613 1078 435 1018 448 966 155 981 650 1011 732 827 767 1194 37 717 1157 1243 206 989 32 1089 451 1123 252 1154 770 879 183 264 423 454 184 892 125 985 779 1184 957 1269 252 458 78 846 135 1349 12 877 891 1344 261 1221 371 985 222 1246 542 733 420 746 159 1392 978 1072 659 868 845 1389 567 707 178 1137 640 1214 1112 1273 364 919 51 269 717 1011 838 1042 329 1036 68 838 356 1244 454 829 140 1003 854 1376 556 924 1339 1348 173 476 220 365 1036 1123 75 429 160 470 583 1154 357 423 898 1310 942 1283 1054 1153 99 1156 109 540 779 1122 156 272 374 1179 222 1133 691 1386 825 886 479 1390 1082 1189 513 890 78 231 260 969 1075 1382 883 1089 85 297 34 1192 569 878 266 1251 737 772 282 388 1213 1255 460 757 311 637 408 522 28 660 463 858 226 250 932 1373 335 1015 277 554 347 376 703 1323 427 1373 180 355 56 618 292 1026 899 1093 56 1201 826 1127 162 250 1172 1253 325 687 422 1021 69 89 28 1271 333 1135 16 287 286 642 136 348 643 836 102 137 571 616 518 798 509 628 477 650 55 228 1165 1299 372 930 243 1269 232 468 183 973 208 318 283 1224 129 959 236 711 359 1149 243 1281 225 1351 615 683 1045 1137 360 1197 489 1386 1060 1217 335 952 379 1000 748 868 180 808 77 848 182 802 1002 1072 224 1017 41 494 681 795 89 330 1059 1155 975 1247 857 1349 425 554 34 1054 195 580 406 1171 41 1060 1265 1379 41 613 87 1143 28 284 1108 1344 397 1202 1287 1373 131 1109 758 1345 278 578 520 644 395 1165 27 360 981 1100 569 819 502 662 1066 1110 159 732 588 618 248 561 613 735 828 1129 834 1190 286 1039 1286 1296 632 1018 1155 1254 319 802 242 997 559 1159 242 584 792 823 227 1357 29 396 328 995 24 257 1057 1158 1208 1220 183 892 217 661 530 768 239 966 496 820 254 1212 189 718 432 859 417 1216 688 1346 55 908 371 472 208 668 624 1219 667 691 65 922 581 1251 41 1364 993 1346 677 1348 711 1252 1280 1345 934 1142 146 538 458 799 425 831 75 1033 229 616 1019 1322 42 892 420 479 53 774 240 913 123 1067 1109 1309 187 771 571 760 718 1012 632 1183 132 913 708 1031 227 1221 989 1151 124 166 382 657 203 577 464 1097 799 1222 478 1092 624 628 849 1039 257 1132 62 916 1136 1223 614 716 148 1041 941 1224 614 1349 460 1074 734 846 1143 1283 79 289 303 909 410 1026 969 1188 869 1323 553 1390 393 781 20 594 120 544 486 731 749 1266 787 1090 547 946 15 224 737 1275 436 639 504 752 299 1283 737 917 36 1153 409 553 88 484 340 1115 4 1183 463 694 744 1094 928 1085 638 661 208 839 110 980 386 1383 274 1217 291 465 622 796 884 912 363 689 398 1263 832 1257 439 621 268 1146 358 1119 280 726 58 566 718 1365 44 1253 346 1293 245 1225 36 731 592 841 212 894 373 1228 48 351 739 878 435 1101 107 735 114 533 1048 1200 770 954 811 1315 752 1021 143 516 124 352 826 1201 87 350 530 1069 232 930 1024 1044 937 1126 12 722 323 935 521 1248 480 485 177 194 702 1130 283 331 85 151 557 1096 33 554 228 1010 360 1075 266 784 184 1074 1161 1383 106 776 709 1100 84 1275 129 1051 852 1381 777 1080 588 895 28 1013 241 360 432 916 471 658 192 519 747 1247 1046 1224 713 1330 169 546 158 1314 721 1157 470 1199 521 1178 867 1214 499 905 1287 1350 727 957 9 612 724 1035 146 229 885 932 248 869 44 1212 404 1346 1070 1110 979 1006 442 760 472 632 725 928 590 1196 1022 1226 109 1121 532 627 397 539 542 1010 441 1242 125 820 1106 1333 501 792 153 625 109 371 504 557 583 793 232 1017 516 939 300 620 1312 1326 602 1328 147 548 120 639 484 554 91 170 478 1147 383 392 422 541 1079 1389 754 928 23 107 421 979 848 1334 323 763 565 851 1168 1182 589 852 404 1299 100 1277 137 1166 427 517 133 323 609 855 896 1073 87 171 390 851 30 950 539 848 383 621 132 312 467 561 754 1203 53 1309 819 1264 486 936 83 720 286 1129 583 1369 619 1343 514 783 624 730 202 902 437 1321 396 448 721 1333 947 1127 420 857 480 632 138 799 373 1362 175 1001 546 555 503 1080 109 647 1079 1294 551 1099 891 954 333 985 208 748 447 861 152 295 306 819 61 1295 122 546 122 1169 623 1025 340 746 353 804 397 1269 1067 1283 124 885 222 1364 119 1231 510 1101 798 843 1086 1254 198 822 788 934 758 1323 31 975 179 330 462 1369 813 1058 1002 1294 506 1258 25 143 103 109 1014 1246 1047 1292 512 1057 216 1236 248 402 426 1221 571 968 415 649 769 931 185 719 169 583 902 1385 684 933 92 378 1261 1295 363 1339 323 737 464 742 192 855 1153 1224 481 603 966 1229 367 447 522 587 537 795 73 967 54 487 1017 1120 237 878 64 356 957 1081 673 1070 30 520 860 912 1168 1371 270 1378 652 657 26 149 391 520 250 731 934 1270 645 1155 366 989 460 780 375 1065 251 1390 2 1276 153 635 637 1052 938 1153 922 1314 749 1135 272 497 326 464 366 790 116 1095 299 811 650 889 764 1183 39 291 71 421 180 1171 789 888 140 173 1086 1155 537 686 171 957 54 874 36 1016 170 1252 1160 1310 233 416 515 1210 820 1050 1117 1245 61 245 350 1319 505 1332 411 1126 445 882 241 1167 47 709 336 817 213 474 89 707 52 655 336 685 636 1100 1114 1119 275 610 94 533 365 810 541 1137 542 1046 163 706 198 303 49 333 560 1089 1360 1390 642 1347 130 1052 532 619 114 651 335 1299 448 569 13 76 1087 1288 260 1341 734 1373 735 1282 627 1167 47 846 37 535 216 1079 210 459 1085 1392 43 1229 326 684 59 89 576 1292 132 727 55 667 526 774 759 1306 279 884 587 894 491 773 944 997 175 1169 571 1341 495 1187 817 1268 1194 1384 360 520 136 558 402 780 204 211 2 1306 361 1328 721 1382 373 395 191 668 217 1193 94 152 730 1113 672 910 16 974 27 438 733 1189 321 564 212 772 505 543 127 933 524 921 641 647 95 1279 280 1283 541 921 499 1392 160 1250 407 1067 216 925 363 1237 484 1144 761 1370 152 868 427 1174 512 778 224 804 305 1331 379 1243 1122 1137 635 1331 375 757 1275 1309 244 888 130 1072 825 1066 412 866 919 1174 483 662 798 1271 512 633 86 871 896 1106 67 878 335 1289 383 604 1120 1209 583 650 427 1388 252 1098 1168 1196 670 1068 845 1073 139 295 8 898 214 286 155 550 1014 1369 808 1301 1113 1255 767 1355 464 872 562 1082 344 1026 622 683 705 1259 302 457 483 489 18 213 534 551 321 1368 869 1051 583 1224 97 557 490 635 841 1233 630 750 728 872 1009 1338 643 745 430 784 478 1307 633 875 545 1267 435 1294 1102 1233 483 807 390 493 11 1163 433 1011 820 1210 355 765 626 963 148 1147 115 878 106 876 347 893 543 1367 1 1107 662 1224 326 435 1182 1325 522 1056 568 731 103 314 674 1171 605 957 10 127 829 1081 814 1266 205 1108 64 99 1176 1194 193 204 430 1192 184 1305 759 1296 629 1084 138 528 1203 1207 917 1101 743 1239 24 155 58 98 755 837 975 1009 423 696 128 328 155 320 725 779 43 237 530 907 96 541 264 824 36 327 39 1101 329 1364 636 1043 424 731 255 988 96 790 533 845 618 895 566 804 194 328 206 1064 345 1000 687 1212 643 674 8 1379 406 1034 180 791 543 1190 380 968 373 802 474 1097 467 1018 817 995 48 641 626 1252 227 679 1066 1197 1216 1367 115 554 475 964 395 936 1023 1215 981 1089 358 610 300 908 680 1073 3 277 325 604 140 257 384 540 98 474 139 301 1032 1119 380 1367 94 382 169 994 520 627 294 1096 430 970 10 77 52 419 713 743 566 1135 197 1260 557 1310 343 805 541 1306 850 1345 680 1329 379 1321 590 1053 42 882 459 872 907 1082 251 498 493 623 279 645 277 446 517 1293 443 611 287 1064 680 1147 957 1137 505 1115 508 1028 248 662 10 433 143 707 78 1141 1246 1296 605 798 575 1011 622 1187 892 1282 500 1082 1 662 64 819 288 528 138 1150 831 1034 295 907 244 827 407 1060 163 516 425 1187 437 1291 1024 1094 285 572 129 662 460 968 508 1375 457 862 246 399 139 221 270 1336 1073 1373 291 443 10 427 83 506 182 1096 498 880 151 370 157 1390 1029 1052 926 1292 34 780 929 950 923 960 604 865 115 1135 11 939 760 998 500 759 419 506 519 1286 540 1377 199 767 266 655 485 1234 648 1333 272 612 977 1029 1184 1293 764 1010 763 1321 517 843 507 1190 555 625 1246 1287 384 1031 995 1042 351 1129 584 1350 467 486 332 954 170 991 733 1114 446 839 44 312 169 1326 22 696 547 995 685 901 431 1273 100 1290 94 250 698 966 783 1025 50 1112 131 530 90 487 109 872 142 775 683 1055 344 1238 128 1118 509 940 149 210 157 354 303 1188 1018 1200 361 629 556 872 429 1155 510 716 50 291 5 355 378 768 13 1046 705 1151 418 1014 71 1042 287 744 35 898 166 323 281 590 23 77 15 589 279 1380 258 870 632 1334 97 1067 228 667 937 1076 367 423 171 1133 113 1002 143 584 348 1250 1236 1327 391 1343 1148 1381 713 1284 95 500 60 1004 951 1343 693 873 421 625 860 942 141 194 563 620 283 412 322 403 529 1228 45 302 789 858 718 1266 362 415 992 1232 257 412 267 1311 741 1389 5 1011 167 1340 732 1308 155 711 680 1091 398 631 90 345 160 702 636 763 33 393 894 1030 24 716 466 1253 572 1304 536 620 467 1303 148 338 981 1330 1199 1343 111 788 688 1352 78 207 650 1223 375 1119 102 827 75 831 712 774 394 1353 145 423 1145 1288 1362 1378 363 1385 946 1077 386 1350 137 1177 99 958 330 457 423 1035 107 603 7 894 146 939 923 1121 170 379 332 1000 79 379 642 1058 78 278 950 1108 727 1179 296 1253 479 1235 665 1038 592 838 493 1290 473 1092 236 570 31 1146 159 685 918 1053 197 467 135 1214 58 121 774 1390 448 1008 88 1140 740 1381 396 1338 51 1189 632 786 858 1169 806 843 194 646 131 870 47 692 349 989 421 502 1290 1361 276 458 1196 1357 1273 1391 198 819 577 681 52 662 435 473 117 1195 896 1265 179 596 695 766 700 1299 410 873 415 1093 497 1296 594 624 9 1231 538 1330 48 1189 90 911 210 675 267 344 57 448 270 343 582 1339 173 564 493 677 1142 1385 50 397 138 1388 360 1316 1126 1147 822 1072 188 1054 202 239 590 1073 470 963 794 803 42 103 1234 1279 107 218 193 254 789 906 726 1088 128 375 92 556 219 1271 729 900 1247 1384 399 581 319 944 442 1198 87 1085 153 1379 72 421 400 1023 585 1031 720 843 1161 1305 133 589 408 1061 447 896 174 563 458 714 722 920 571 1070 528 1243 10 982 467 691 495 907 546 1332 284 1259 200 1297 825 1080 1133 1318 902 993 238 1214 104 1302 183 300 614 843 250 1067 945 1251 17 77 249 1132 868 878 675 748 464 1126 147 180 419 984 1338 1358 253 294 1003 1291 107 1252 355 1036 234 774 882 1208 401 600 1217 1332 118 821 494 551 74 814 111 1126 732 1134 551 953 119 782 862 1372 650 863 823 1276 741 1257 267 799 51 83 274 552 152 1370 460 944 403 1072 190 989 194 358 849 942 67 366 44 60 1328 1374 595 818 1148 1309 882 1299 1222 1270 492 822 350 744 293 324 864 876 858 1359 168 670 1018 1120 673 830 624 1354 210 548 850 964 327 762 761 1352 1248 1367 721 974 965 1351 487 589 508 1256 859 1011 154 761 17 1272 4 939 592 1007 1240 1380 321 332 1205 1290 998 1117 101 324 605 892 1008 1214 496 951 654 1012 459 1371 278 1315 523 970 597 899 31 772 1117 1250 644 1389 341 1368 463 803 151 843 630 1052 1053 1267 655 857 530 563 1032 1084 144 464 567 1147 152 704 1038 1336 105 549 40 678 281 777 856 1137 216 1130 906 1049 350 674 1036 1075 903 1350 973 1116 681 1114 795 1088 502 1108 471 524 53 593 881 1033 185 619 490 1045 785 1069 573 650 345 442 110 1241 432 967 104 883 421 1380 1010 1381 186 207 284 779 353 1113 1145 1162 134 864 1225 1292 569 675 344 611 750 817 202 238 595 1348 739 1272 375 663 1307 1334 632 1010 328 466 230 270 451 909 687 845 98 374 649 1034 798 1313 827 1178 428 756 262 834 468 1347 494 1088 1124 1234 612 1291 756 1285 1362 1371 97 862 538 1202 711 1381 428 1328 324 1060 806 1258 441 455 302 791 203 642 25 227 77 1160 911 1268 633 938 167 1013 1145 1381 474 832 240 417 536 1299 196 681 265 1353 322 588 113 1016 303 379 741 1054 339 703 423 1265 366 775 1019 1088 194 1098 1350 1358 256 264 904 1360 935 1045 827 945 795 1273 361 546 666 779 862 1173 74 525 428 1040 590 1185 661 1247 246 723 260 1087 202 1311 447 1149 66 581 388 549 728 1277 49 78 146 1143 315 1061 829 1242 86 399 369 1068 290 982 976 1123 975 1191 95 447 534 545 88 734 319 845 278 354 395 482 634 1057 244 598 304 605 18 676 535 1301 1197 1206 192 1082 234 389 90 1302 227 961 82 616 1199 1356 913 1169 485 1368 581 1275 743 1234 278 1167 392 1105 554 1040 838 1116 936 1320 312 713 509 1348 1126 1283 659 1382 141 1015 551 717 470 513 207 1025 1034 1334 551 797 719 1156 41 1150 24 782 972 1010 159 1305 409 1196 5 1299 139 1013 366 615 460 597 1295 1351 877 1177 15 592 366 522 395 447 423 891 298 1160 349 1202 680 774 376 1208 778 1133 474 549 220 1042 789 902 834 1312 8 903 297 313 500 884 326 1141 621 1086 888 1061 36 1159 73 503 305 596 258 938 75 124 317 1164 1124 1181 635 1161 670 1016 311 1161 124 872 178 310 109 1181 525 1328 1070 1104 23 809 946 1017 635 983 668 1369 557 1155 673 893 468 1337 505 1018 296 1087 766 1384 54 1382 940 1226 555 1342 107 229 799 1155 527 890 600 628 274 1255 885 985 485 920 854 1198 1001 1010 938 1232 90 965 317 1292 747 846 127 768 510 1300 434 1038 595 743 80 615 931 1001 243 1056 395 835 1122 1364 38 570 371 1246 163 1125 184 605 139 1009 234 1261 515 1068 380 1146 226 1265 206 923 270 561 645 1035 819 957 624 948 1070 1381 78 1216 368 951 832 986 599 746 407 926 250 1049 618 1041 65 1104 95 119 244 338 560 997 87 594 632 1062 928 1073 707 736 767 900 757 1096 51 380 52 735 555 590 576 1002 696 1040 11 1027 422 1159 1176 1320 71 1273 632 1390 1052 1062 182 1289 369 606 403 486 40 1001 834 1119 297 1040 459 1190 400 1100 346 1014 793 1020 802 1032 303 1313 172 612 48 1118 345 488 25 40 362 379 1044 1389 225 332 85 369 235 702 799 885 524 1094 56 234 21 1294 118 771 88 803 527 903 457 1170 995 1217 221 406 118 1122 486 558 455 931 425 958 44 1003 1133 1177 229 237 132 693 308 678 252 891 472 579 1256 1274 293 694 205 569 370 1155 330 540 119 865 155 930 188 287 742 802 43 1131 417 1248 444 1257 632 772 287 463 763 994 540 1337 941 1390 832 1142 433 664 144 667 939 1180 131 874 414 598 183 928 348 1382 130 282 74 1159 310 531 725 942 483 1166 370 1316 565 754 128 1061 380 1133 708 965 109 114 886 1129 553 1017 645 1071 358 1358 1008 1060 271 1193 553 594 325 944 654 946 339 468 581 912 342 875 197 370 109 110 46 147 21 286 616 852 758 1164 97 772 361 1196 309 1128 375 1275 560 1309 493 819 885 1334 53 821 639 960 495 917 60 65 459 728 189 1072 479 1163 988 1289 734 865 335 761 1086 1209 524 706 229 1245 99 822 481 838 410 589 184 1091 888 1195 207 1264 976 1317 567 994 197 1251 801 1247 573 1008 207 348 227 1297 927 1167 391 1199 201 1146 46 217 246 335 153 901 473 1053 621 1003 275 355 664 1018 607 742 125 438 602 763 559 996 392 917 16 520 163 846 658 844 386 570 34 1110 1056 1142 171 188 427 1321 465 1126 18 82 328 1040 876 887 15 1082 94 703 832 952 812 827 920 1036 446 1075 228 459 632 904 114 149 496 1227 284 555 616 1363 439 466 52 412 440 522 387 802 1178 1288 1186 1301 1249 1251 247 1172 619 766 278 694 550 1116 871 1092 1069 1260 523 932 567 1175 600 969 488 1146 832 910 31 1335 63 1035 458 1181 531 615 126 741 210 1192 995 1376 673 1061 207 787 473 658 601 1009 278 829 918 1226 234 694 48 600 740 1203 157 641 910 1021 168 603 102 927 700 1133 104 331 703 1097 591 818 834 1180 1256 1291 1255 1276 103 944 84 216 745 1146 337 881 463 1361 1112 1159 293 509 57 202 1054 1062 763 853 672 1063 681 962 161 986 399 466 176 765 215 697 807 1254 220 748 142 1324 424 1220 535 1274 497 1234 233 788 184 1219 691 1193 585 1275 437 946 277 617 930 1105 12 887 498 845 336 423 961 1154 231 525 7 773 78 469 164 187 540 1374 1085 1329 475 1156 1047 1076 6 380 125 128 710 754 21 900 128 650 82 1299 336 1209 842 1085 44 483 316 619 477 869 529 716 328 1155 342 669 370 867 141 1000 359 1167 729 1094 1041 1323 337 936 20 1094 79 780 1199 1377 800 1143 572 1218 924 1012 863 927 613 1227 414 635 297 994 551 1301 713 1179 740 858 380 529 425 1133 480 873 3 349 863 1083 898 944 1169 1176 55 1128 1068 1174 534 1034 2 120 129 1299 219 676 31 119 31 94 39 1060 917 979 106 1142 405 1168 363 693 756 1326 154 964 273 887 374 1062 1271 1369 892 1171 344 902 394 529 586 887 712 777 131 894 829 991 496 1149 297 1167 1196 1210 809 1200 1050 1349 39 709 717 1058 464 1104 165 791 251 1072 230 1307 30 180 183 330 356 946 917 1007 29 940 795 947 726 1024 2 1051 346 1185 473 501 685 773 1081 1129 144 277 418 863 52 514 317 786 168 1044 166 194 418 491 252 400 118 1077 349 811 245 1120 593 1255 65 586 1180 1249 379 809 24 1274 311 926 1064 1313 367 1330 574 880 441 1248 13 183 72 814 108 1306 419 730 852 1335 78 103 894 1377 483 1214 602 1001 1007 1373 1171 1229 918 1317 196 851 436 1199 289 1323 67 727 183 1040 145 793 88 712 769 906 570 903 65 1262 130 930 436 656 170 1311 702 1365 824 910 851 1309 665 1281 1093 1189 858 1031 506 757 415 1366 84 1092 134 1268 79 1318 723 1017 446 882 441 522 78 1209 525 831 706 753 467 815 202 434 684 843 876 1165 31 73 174 943 88 666 486 491 1018 1178 174 1350 137 360 533 1167 153 1019 189 1317 699 740 343 800 448 1007 719 1108 767 1339 245 955 37 810 117 175 75 899 744 1196 39 249 847 884 886 1202 332 1224 606 1171 213 907 857 1090 107 381 414 1053 485 858 879 1326 317 741 616 793 204 1010 1144 1348 657 1259 612 1102 591 1373 881 1188 1050 1094 1092 1390 836 1221 181 666 218 1297 497 623 940 1217 817 1262 410 1002 252 552 153 1359 215 1206 216 1037 1281 1380 833 1257 514 709 428 517 114 265 36 214 425 1377 962 1275 842 1181 147 1328 404 883 254 1111 235 648 68 1090 902 1208 190 728 894 1189 449 719 327 891 628 1011 229 1061 91 328 1107 1239 737 770 1005 1095 634 1035 68 225 106 926 837 1261 41 302 731 1217 851 971 164 774 377 723 572 817 799 949 42 863 223 995 1081 1276 572 1387 956 1282 985 991 14 1257 112 884 1084 1140 668 1289 469 1237 214 788 153 1362 224 527 156 1027 42 303 611 1324 163 1104 331 616 848 932 356 710 688 798 935 1073 512 816 804 1069 819 1277 64 277 213 423 657 813 806 976 836 1159 62 736 456 816 112 1108 768 991 257 518 315 905 274 896 604 625 578 1167 25 1000 450 503 605 832 462 1288 594 800 715 1019 1069 1357 366 1095 564 903 1016 1167 49 1288 410 1009 653 1079 572 1135 137 1158 572 754 109 586 1108 1211 1351 1373 635 1022 94 1317 420 772 601 1295 323 685 57 896 448 1286 745 1387 441 1292 109 928 199 781 55 1062 553 732 322 908 57 1291 1170 1295 27 1372 42 452 369 521 315 836 121 696 280 1073 959 1080 57 615 99 508 241 392 763 955 563 984 636 657 265 1248 599 1225 109 932 672 880 168 302 914 1162 201 1325 385 863 845 1100 901 1296 459 1364 964 1309 921 1138 696 792 4 1208 259 959 943 1356 798 1111 18 659 249 1242 243 912 421 1363 914 1022 65 1118 354 1363 34 1038 443 1052 544 968 96 977 109 724 192 833 320 1168 413 1312 115 730 174 833 461 626 129 216 563 1142 829 1084 860 1272 288 1099 350 1078 759 1190 360 835 73 1157 135 946 246 1307 176 343 665 997 176 1256 709 974 737 1282 511 1366 958 1124 720 1258 594 795 901 1033 328 363 18 254 114 777 671 920 614 912 946 964 826 928 79 772 737 1074 860 991 726 794 59 1014 1130 1274 422 1193 1145 1334 45 523 551 1366 84 473 755 971 65 1127 398 924 203 836 342 1267 938 999 643 995 130 744 614 1240 664 789 393 1253 43 88 276 481 642 785 594 627 105 260 253 696 293 993 607 1241 349 1234 933 951 289 825 934 1218 631 798 103 548 263 1120 234 604 129 208 586 1102 186 1192 694 1153 211 926 392 1200 1230 1351 6 571 510 1207 1189 1296 358 688 1051 1332 531 1288 406 1288 656 1026 215 1253 272 362 888 1292 173 1092 312 1272 557 989 797 856 214 1253 318 529 94 530 1298 1363 654 1262 419 726 160 786 1008 1392 68 883 582 996 246 283 973 1007 347 463 1064 1162 297 669 666 1140 209 1051 919 1034 471 681 718 926 881 1203 603 1341 379 537 735 890 707 1289 450 1040 527 595 426 1282 799 1030 252 855 1065 1269 690 722 394 1192 583 1329 474 1093 399 1218 815 900 475 773 92 1139 989 1204 271 1025 269 636 666 868 616 838 941 1227 509 848 242 677 234 1268 508 637 760 1178 176 1316 8 816 4 145 289 976 591 1318 273 927 1107 1319 762 1270 57 1057 89 1063 1093 1175 183 1328 38 971 72 999 510 939 93 814 370 628 661 1200 71 456 28 794 560 617 785 887 127 205 26 834 123 464 888 1064 989 1298 754 1341 589 1240 10 816 345 1261 576 1086 345 1235 827 1305 442 481 248 461 892 943 80 1159 957 1103 210 1183 647 861 516 1293 832 1367 487 1015 549 840 701 1092 737 1312 589 1278 778 1106 12 933 294 652 618 1008 712 1297 853 1037 108 194 888 1248 113 985 584 589 569 1234 697 825 136 205 458 1137 133 662 43 730 439 1270 285 916 245 600 512 676 771 1183 149 336 206 242 655 1130 148 1194 828 1372 306 309 290 418 124 1126 123 580 232 244 391 872 758 1052 589 776 81 581 647 802 351 1130 889 904 1043 1374 22 1345 544 1339 55 1319 770 1235 361 1238 145 414 110 1387 476 1354 564 1074 365 885 617 1007 677 1056 70 691 781 1037 316 735 63 498 47 738 1042 1333 153 1198 774 1008 460 796 442 1279 977 1112 923 1317 540 568 757 1166 47 1001 609 1306 665 1000 965 1323 657 682 312 1182 224 1203 692 835 50 582 511 982 307 1036 453 978 347 432 580 1382 43 1347 68 1138 401 869 294 1373 1197 1303 1295 1346 772 1368 605 616
Output: 5

Example 2:

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

Example 3:

Input: 1283 1282 1 1283 220 958 45 1045 652 694 158 422 703 1124 885 1181 236 551 975 1226 973 1238 510 902 495 642 5 809 413 760 597 1109 658 837 170 692 153 307 1185 1220 180 935 1039 1115 106 163 83 804 350 1085 611 948 193 808 467 612 565 728 611 999 973 1048 465 982 208 1129 64 780 596 768 708 955 277 620 526 935 430 981 402 693 870 1069 1122 1130 316 377 133 1057 361 761 54 736 62 667 285 828 1229 1234 30 976 636 724 581 814 667 1202 310 581 55 82 881 954 490 925 387 931 35 335 346 628 157 616 105 214 68 1267 264 583 1149 1154 603 786 359 1185 195 588 797 1056 321 1040 102 1017 990 1275 331 971 431 1089 531 1093 1070 1274 360 1169 193 1033 951 1126 889 1150 772 951 85 262 41 693 342 536 194 950 744 894 961 1023 266 765 380 1155 432 1195 585 1092 334 463 167 764 83 221 36 832 797 833 548 970 391 1074 67 274 286 376 328 401 125 857 8 89 612 721 63 632 587 736 793 1028 400 611 327 1108 998 1130 1 1140 183 1036 120 300 155 735 163 716 265 784 461 1108 325 357 8 906 1149 1228 575 740 684 1119 463 875 42 337 940 1048 395 829 803 827 800 868 545 626 545 944 306 332 880 1214 11 453 59 84 311 564 189 360 1161 1198 144 263 337 538 1001 1038 785 1131 131 374 858 1011 487 998 856 1184 84 305 324 1250 590 664 390 1170 891 1280 927 1107 613 1057 234 532 662 769 663 841 169 411 299 1042 78 658 262 984 239 886 449 996 980 1242 84 605 345 1279 191 1110 3 110 866 939 555 1136 207 814 873 983 212 869 200 1124 444 718 118 169 491 539 399 1079 18 852 127 175 351 1047 479 1112 151 612 56 514 413 671 854 1168 480 889 783 1220 386 1242 872 953 722 983 256 1281 140 362 456 899 530 871 60 106 224 436 700 895 636 789 185 983 203 254 734 979 384 887 1076 1121 601 1082 747 1275 686 1151 32 1055 169 1188 63 511 96 751 317 692 937 998 129 735 158 834 275 690 466 1197 516 1084 1014 1145 357 1222 57 808 99 871 494 729 892 1054 266 324 197 708 325 460 620 1260 649 710 279 918 174 853 381 1258 218 366 780 877 551 1091 564 921 625 1048 142 606 20 669 1037 1161 89 315 518 1064 284 1169 863 1185 820 897 1095 1175 545 1028 551 836 490 542 858 928 449 937 455 1136 326 1095 14 22 131 952 765 837 351 770 192 336 1129 1134 786 1145 354 592 780 1283 512 861 86 1240 455 489 278 805 490 853 245 992 871 991 970 1254 587 1135 775 1192 1007 1131 576 749 272 688 434 591 392 597 159 1135 216 953 614 945 545 1101 797 1242 478 1123 612 774 1189 1277 1116 1278 10 592 118 1031 656 683 686 972 70 706 95 105 44 101 954 1255 700 870 319 323 907 1045 171 977 828 886 74 988 1127 1167 659 979 843 868 185 468 168 403 230 908 741 1036 328 772 795 1205 219 1283 904 1023 198 1141 884 908 318 429 511 1203 275 969 887 1090 12 355 493 1209 358 599 640 1034 149 1160 586 1144 941 1064 639 857 790 1170 514 1142 661 1116 1025 1282 690 917 528 875 293 604 384 802 353 1014 98 903 494 1013 285 583 797 938 115 845 879 1010 778 1077 472 952 212 301 391 1194 274 1053 324 577 534 738 322 691 128 579 834 1116 423 1173 106 431 348 413 225 282 1116 1186 56 733 465 1215 46 440 129 917 1030 1191 561 1136 60 936 169 1175 223 1264 916 954 737 1016 779 834 262 857 388 506 81 1215 158 495 190 462 931 1116 765 1120 373 904 1035 1079 351 536 447 1121 71 840 539 1131 20 896 6 763 152 611 426 1049 794 1143 50 693 106 169 348 616 169 917 602 902 93 1048 11 1125 692 1143 758 786 463 573 615 777 549 983 886 1006 782 994 477 998 297 991 498 775 234 1159 685 1135 415 790 417 466 806 913 1136 1181 1 160 109 776 158 421 15 66 585 1211 587 962 311 1174 604 663 454 889 36 119 413 764 82 186 20 194 307 1008 1068 1173 331 1041 258 490 360 762 279 698 533 1269 111 1234 151 311 543 637 1102 1182 324 853 686 1072 967 1097 600 815 492 624 320 1194 272 1196 600 972 22 168 4 1220 1028 1231 164 264 1174 1249 599 1163 371 537 212 1282 76 408 265 975 290 318 209 730 487 868 326 1024 238 765 2 535 356 1095 429 672 608 905 206 1145 290 634 340 670 6 16 321 755 49 398 276 1095 298 678 29 1002 666 1165 70 861 28 838 283 427 1064 1165 609 926 642 1064 817 870 1094 1167 246 713 136 1248 582 629 406 1213 316 424 10 1116 295 1021 88 199 866 1184 732 863 381 529 965 1078 77 430 9 848 711 729 350 368 87 715 734 1066 119 1084 585 792 665 910 177 767 173 907 765 1046 26 604 339 730 428 783 31 319 436 1001 137 1217 876 948 770 862 42 901 771 1282 400 886 676 1175 642 1189 325 979 1133 1193 953 1060 297 1205 222 854 394 459 505 905 398 916 476 1251 535 912 44 865 226 1202 534 948 187 541 755 1102 242 991 188 396 350 1036 158 929 1020 1125 836 987 917 980 1 107 959 1003 634 641 501 539 356 739 292 1134 926 1269 803 1060 690 857 394 1193 840 1237 534 955 570 829 316 688 896 1179 830 1159 391 1223 571 690 552 1176 1025 1229 1123 1167 171 389 315 647 948 1272 746 1099 588 993 442 908 547 853 271 721 406 576 266 306 127 1156 38 978 1156 1191 425 591 446 1179 471 483 607 850 860 879 679 1035 588 674 223 736 235 971 232 280 186 1116 389 1035 396 1113 135 151 82 1156 815 1207 129 566 706 773 226 949 544 971 260 315 38 99 690 1279 171 571 289 1051 294 892 177 433 519 710 1099 1260 251 901 83 310 10 449 180 581 726 989 578 1260 1188 1252 572 1075 931 1221 87 367 165 701 285 844 87 742 574 943 182 940 406 959 252 254 410 1004 533 886 1136 1254 449 558 924 1194 248 970 28 562 205 834 693 996 675 746 85 986 376 797 375 1127 236 1208 279 893 135 910 228 676 30 707 745 1211 114 878 1073 1097 184 755 376 1154 657 721 668 1048 478 783 536 918 13 87 1204 1276 359 725 721 1245 819 963 281 1145 346 931 311 517 426 705 686 720 1044 1252 51 935 288 1221 116 133 158 1114 337 408 729 1239 196 431 269 901 299 1131 329 1197 108 681 121 923 20 512 161 436 759 787 964 1247 188 364 400 964 466 997 389 660 361 550 243 1283 551 849 207 1009 321 964 494 776 670 930 229 246 772 1068 407 746 176 691 201 748 385 1063 200 1058 240 495 202 797 92 519 487 1262 158 412 887 1197 345 347 678 1077 208 1132 492 1070 10 201 324 865 803 1118 437 858 564 627 20 1242 21 671 769 945 212 996 964 1170 204 681 95 1004 311 398 84 436 931 1016 48 420 806 1142 28 1106 839 1193 445 786 158 510 205 942 84 816 6 536 372 812 268 1067 338 442 1137 1231 24 746 772 1142 619 954 225 769 150 224 1084 1144 261 458 18 1001 244 769 146 875 273 1167 344 693 229 650 270 772 693 1233 426 847 823 1257 1159 1254 513 645 11 555 51 260 400 678 556 681 896 1148 1 1197 211 367 27 539 98 1019 520 611 418 864 757 951 710 828 109 535 37 506 353 488 3 224 151 569 507 1248 767 1103 325 684 618 1239 430 1161 330 615 257 854 321 965 421 900 534 655 1036 1088 42 1123 343 406 23 200 114 314 299 522 1116 1135 388 723 268 852 527 1018 280 1159 335 1061 141 961 310 799 134 873 400 845 266 838 39 710 130 963 483 1077 500 1261 1025 1235 249 1197 1065 1172 158 362 124 562 692 1097 575 676 177 533 719 1099 498 551 508 678 187 1269 90 311 591 756 357 1211 304 855 158 400 463 1197 678 1211 249 697 457 681 840 1180 1108 1279 178 1066 835 916 859 1260 154 577 980 1183 416 484 702 1005 207 1275 677 888 289 916 170 1167 235 533 187 395 899 965 973 1210 309 517 957 1184 73 98 531 1039 60 108 112 368 12 837 782 1099 226 1187 215 620 1248 1278 840 1232 133 634 414 579 922 1245 483 1241 79 751 709 1205 253 973 633 1077 906 1256 220 629 381 1276 17 640 510 1027 243 1070 765 1116 497 994 898 1183 283 1278 293 1268 420 434 356 560 807 953 137 533 481 1129 365 1104 199 608 112 285 782 1001 208 1112 72 851 713 952 25 427 123 427 557 841 353 451 634 809 448 1150 915 1139 33 659 811 823 356 646 660 791 826 1093 165 1018 566 1209 117 550 462 869 255 689 395 648 334 883 981 1045 934 968 394 1100 142 1252 213 1095 304 386 1136 1251 758 781 418 1043 801 979 193 1176 379 1177 192 994 690 1116 828 1167 464 1266 42 1019 291 1209 488 1054 551 823 552 664 988 1150 455 963 822 1182 868 880 769 1082 674 1227 842 937 456 687 499 1105 430 443 495 1190 172 1183 998 1164 47 530 366 1032 630 690 869 1157 536 642 360 714 327 540 404 697 477 515 682 799 516 686 319 1258 147 969 686 1181 400 1075 114 134 138 612 265 1273 369 1114 574 850 419 1052 482 1068 1160 1172 100 1267 393 766 69 1221 469 1215 753 1023 28 485 704 762 302 872 696 1053 398 886 413 786 217 767 391 416 371 911 617 1267 566 851 692 717 669 750 754 1232 52 1163 440 1197 299 1107 237 520 439 755 381 548 985 1092 439 867 454 1025 7 973 450 495 191 492 434 771 457 1281 105 953 106 940 341 1188 17 428 290 1175 14 276 369 378 758 1071 1018 1280 441 1202 250 462 267 705 920 1128 145 382 363 845 300 483 1022 1096 383 1100 508 1010 947 1250 162 612 129 1013 629 1080 370 660 60 567 122 916 886 1237 595 1128 857 1197 426 694 263 460 218 1270 233 292 210 667 310 371 579 787 239 644 432 664 653 1220 356 365 495 920 743 1013 473 1143 567 1218 254 1117 567 1265 103 839 810 821 486 846 171 1254 728 1278 880 1178 412 782 396 994 1109 1120 209 1244 588 1014 755 1022 533 968 604 1263 656 1003 1231 1242 139 829 296 689 303 584 406 638 272 545 1230 1234 86 1145 1 1121 323 882 632 1158 523 1017 976 1124 312 1167 782 1253 659 995 152 513 65 591 982 1116 126 436 143 904 607 651 509 932 132 870 366 389 788 930 321 1201 314 568 622 875 564 805 40 973 322 940 181 980 654 871 34 918 91 1240 262 496 353 914 340 610 113 479 283 1225 989 1208 363 956 354 1153 384 589 437 623 335 449 1155 1279 831 1161 778 810 905 1013 506 968 909 917 94 522 440 593 419 825 933 1130 621 1074 265 1145 217 261 1026 1087 841 1077 703 812 287 983 131 158 19 1001 239 761 128 374 605 1083 249 475 108 179 10 870 1135 1152 690 1002 438 1174 642 991 306 313 374 419 695 938 48 727 507 946 241 403 588 594 416 576 60 958 227 385 643 676 153 510 919 1209 297 824 10 225 156 700 262 1202 382 980 227 473 771 1160 112 1219 612 777 111 1029 29 1224 548 1131 259 833 139 1166 379 677 478 694 873 1001 841 1266 40 1261 689 1234 736 850 274 886 405 1159 32 1037 26 1117 699 1036 449 966 360 394 3 209 1012 1206 391 1135 100 782 470 716 239 818 705 1021 509 986 680 786 899 928 43 244 58 1186 581 772 400 751 418 660 16 1138 409 654 690 849 636 900 953 1231 684 1146 158 820 760 890 290 1026 503 1078 121 487 237 992 352 1123 598 808 631 686 659 1200 426 813 80 1156 244 527 308 1184 664 752 118 444 703 1077 846 1040 341 957 546 560 108 1243 247 1078 504 1094 299 974 320 559 9 700 975 1246 1093 1211 482 502 339 960 525 563 194 393 316 1050 254 524 3 1283 384 1086 700 1015 432 1216 97 761 393 1206 84 1111 93 712 1140 1212 865 915 874 1236 379 1117 673 1148 20 511 581 970 194 231 148 917 499 975 874 998 289 333 895 1259 75 1215 1157 1162 548 1145 51 580 104 363 1199 1235 381 839 45 798 76 1059 430 1188 53 111 521 917 442 971 553 610 744 1091 677 1147 1023 1123 676 1062 1082 1171 731 1257 435 1028 670 675 452 1014 102 1197 436 474 796 925 198 863 596 1181 358 1180 266 1005 61 1282 397 903 222 1081 166 630 107 543 838 1129 854 873 928 1271 349 1069 918 1098 15 641 13 20 584 1262 605 1000 552 1197 554 736 563 992 134 635
Output: 13

Constraints:

1 <= n <= 1435; 0 <= m <= 2870.

Loading...
Test Cases:No test cases
No test cases available.