CT29218

The corridors Fewest Hops Puzzle

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

It is audit day at the copper works of Verdigris. Rhys spreads the corridors records across the table and picks up a sharp pencil. 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 <= 1973; 0 <= m <= 3946.

Example 1:

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

Example 2:

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

Example 3:

Input: 1934 1933 1 1934 173 526 1075 1246 1454 1515 474 657 369 803 200 920 720 1116 271 412 77 720 447 919 1053 1141 336 393 543 575 36 1245 203 1788 371 1021 101 704 1398 1651 941 993 770 930 682 1245 434 1404 101 875 80 818 432 1122 995 1914 491 1794 423 1792 626 1171 432 555 405 1780 544 1677 317 1625 1375 1720 299 1543 96 1528 233 437 127 838 669 930 220 1193 560 584 1194 1425 667 1225 840 1315 1263 1466 81 1002 46 551 1210 1422 67 1329 610 1803 1535 1655 17 1541 928 1184 542 1043 478 923 232 570 456 540 1644 1900 21 150 248 679 985 1782 916 1339 406 983 94 1093 467 1643 177 743 62 1492 146 1743 354 447 280 1743 1212 1742 62 1043 1436 1773 1731 1782 1185 1821 486 1314 1874 1932 398 519 454 1173 165 731 881 1200 165 1875 183 1712 542 1509 1026 1206 515 1058 522 1820 485 753 53 321 1378 1774 1382 1764 548 1194 361 766 95 1497 825 1404 357 1326 586 1389 444 1419 181 1630 155 1822 952 1297 974 1771 400 693 423 557 201 1431 960 1020 1351 1473 1483 1642 1080 1149 682 710 34 662 1734 1806 1277 1692 125 1283 51 389 1140 1651 516 944 593 916 480 1765 704 1774 1093 1733 442 1846 1732 1855 469 1005 957 1385 412 1366 1026 1807 903 1667 1717 1748 468 750 690 801 918 1485 359 848 91 1141 39 332 625 653 412 1190 1231 1377 250 1453 1270 1614 1626 1701 168 1089 218 1155 996 1672 969 1213 473 1204 129 160 729 1287 1211 1907 643 1006 1516 1741 617 706 143 1147 1358 1674 243 1867 1283 1699 580 1328 62 1530 1039 1250 476 1918 69 1367 414 1446 648 855 3 257 92 705 1203 1511 692 1241 245 1829 585 1934 19 1622 601 778 313 1654 760 848 132 1037 417 1910 1096 1701 472 1028 1526 1826 1284 1564 1047 1141 406 951 936 1919 1331 1503 1205 1729 1257 1520 1169 1231 57 1587 603 1245 413 1027 432 799 945 1544 1671 1684 182 1010 152 900 625 1777 529 1916 1321 1351 378 1389 231 677 1044 1136 513 1323 258 646 338 1404 1043 1624 159 1130 39 90 152 1491 238 541 724 1745 344 1145 371 1047 309 1930 1627 1915 402 1933 1653 1714 765 1677 322 1094 796 1526 160 1194 97 927 93 798 927 1388 1501 1549 506 617 242 1544 228 1012 96 1034 666 1181 529 636 91 552 1368 1584 456 1796 34 926 200 1067 797 1627 828 1689 32 348 1207 1832 381 866 1331 1466 235 1738 402 762 749 1315 1194 1707 520 1610 679 1000 609 1126 954 1651 674 1883 451 920 630 1817 145 494 1384 1438 742 880 1189 1766 105 1376 888 944 330 1112 178 1901 243 1795 986 1903 490 715 803 831 471 1333 885 1823 1114 1733 1156 1263 1099 1308 194 1136 399 1270 1431 1825 38 595 943 962 136 991 884 1079 465 1007 1639 1855 333 728 144 758 643 1896 1240 1369 1243 1684 500 534 450 461 890 1559 621 1179 311 1630 1524 1805 713 1677 1082 1893 57 1029 1148 1336 76 1735 4 449 557 1164 894 998 153 1560 1686 1691 236 1912 106 245 769 815 427 1212 89 244 166 355 1388 1727 164 1719 444 1056 1512 1583 153 1706 315 1750 528 1040 1649 1709 1322 1637 1122 1302 551 1744 84 1598 382 687 394 997 1754 1797 1195 1789 115 865 1870 1920 67 316 41 254 920 1796 113 482 555 1545 1426 1900 74 138 1303 1674 677 1766 324 1141 1107 1460 22 92 310 441 68 1585 1178 1217 1337 1751 1023 1712 819 1824 352 1098 1113 1872 52 1675 1424 1672 1487 1537 864 1148 725 853 753 1796 522 684 744 1739 14 766 113 1052 1115 1516 1421 1850 124 1618 512 1110 1522 1534 1402 1859 261 1199 1465 1698 472 1927 271 1396 218 1213 1564 1752 102 304 243 1635 247 1313 1682 1889 437 1395 356 410 1250 1888 768 1584 48 1865 784 844 293 298 1044 1596 459 687 243 545 1353 1510 1117 1921 1070 1255 225 1343 595 1530 633 1793 699 1823 287 1769 39 1727 466 1813 399 1248 1255 1911 1238 1457 169 431 149 1325 21 686 350 1595 1465 1490 618 1231 1027 1425 1650 1701 196 1840 423 1751 64 732 200 821 1224 1227 1011 1777 619 1254 207 396 165 981 943 1024 1195 1901 1031 1097 312 1654 595 1314 1396 1683 1727 1797 129 1152 150 1764 461 979 1535 1599 555 1202 39 483 1691 1749 1419 1633 423 1094 954 1296 660 1356 529 1018 860 1854 974 1662 459 1330 693 1538 15 1849 58 511 578 1934 448 879 487 1677 39 1778 490 1267 190 1261 330 1710 40 342 705 1629 1675 1878 844 1038 973 1173 73 433 302 658 908 1603 693 740 75 1245 281 479 417 1901 896 1178 144 1383 393 1553 415 1384 718 1595 999 1473 456 1642 1645 1851 812 1233 581 1899 993 1834 1386 1675 388 1282 519 1406 783 906 101 1485 647 682 545 909 235 1387 1228 1809 611 736 1434 1481 599 1900 1360 1891 505 824 1379 1707 114 849 704 1004 317 691 845 1010 1330 1755 1245 1561 116 1277 198 1273 201 475 235 1014 35 1234 238 959 1399 1848 421 588 339 530 837 1721 37 1579 1528 1850 461 1421 1728 1740 832 1443 193 1347 73 902 803 1343 461 1749 449 1421 1494 1598 747 1374 675 1849 1599 1862 302 1593 1095 1638 330 493 1078 1607 1101 1656 981 1773 972 1565 123 1390 464 1301 1369 1603 199 1440 692 944 26 1628 63 1417 724 1500 861 1146 608 893 1002 1768 153 611 1371 1559 4 418 60 1746 418 807 1190 1730 734 1374 172 1015 299 1183 1159 1187 490 765 169 543 850 1800 394 707 444 1886 37 127 657 1300 52 1598 202 692 529 751 891 1346 551 1782 1123 1839 207 337 177 770 1200 1907 763 1556 498 1466 1452 1600 1787 1883 772 1210 403 1571 1209 1842 105 357 202 794 1157 1272 1035 1404 442 1284 89 1682 89 1375 219 1885 87 1535 18 1058 984 987 677 772 1202 1636 219 1093 591 1664 470 532 487 936 217 728 1089 1928 265 1078 965 1634 61 1785 977 1910 91 1744 612 672 173 1581 76 911 7 843 1433 1444 1812 1891 662 1416 670 1757 1243 1722 200 538 296 348 1112 1121 16 865 947 1448 912 1395 110 368 311 1031 1365 1693 586 1129 1306 1397 12 1680 325 424 153 1130 227 1573 59 65 252 1650 931 1069 722 993 1536 1572 741 1093 1395 1423 450 622 485 1837 5 607 927 1259 585 1017 171 1338 10 1071 1560 1772 571 1223 806 1248 568 698 271 1143 422 742 1271 1373 446 1776 715 1195 62 1462 491 1407 604 1620 541 955 970 1144 438 978 1676 1721 207 1696 861 1507 1078 1836 1355 1596 325 953 22 571 180 849 1248 1513 10 1396 444 542 392 1283 486 1630 139 1141 267 1022 947 994 748 1331 974 1240 400 987 932 967 488 1035 106 1909 804 1528 195 635 586 1195 446 948 530 1823 883 1130 1218 1453 132 1868 665 754 207 1581 280 1242 899 1270 149 1533 903 921 638 803 521 1364 937 1406 644 1438 7 563 1544 1904 158 1543 89 224 348 1261 93 1775 441 1472 903 1519 749 1420 954 1246 147 645 244 307 728 892 825 1142 5 128 920 1093 1525 1630 1138 1588 105 1195 1166 1277 730 1468 788 931 449 1074 592 677 156 1296 1106 1711 528 1395 1073 1330 1081 1206 1782 1842 53 271 13 1559 803 968 139 715 727 1926 45 132 1074 1674 627 891 1404 1560 541 1770 133 848 353 1806 468 1493 651 925 144 1448 1266 1679 521 976 1488 1648 1469 1540 200 673 433 1779 411 1770 337 1740 1122 1508 1704 1774 231 364 615 935 1192 1817 369 765 203 1577 998 1116 1291 1719 376 439 884 1742 947 1467 462 1466 761 1699 760 1630 256 1208 1087 1571 288 769 803 1800 629 763 1741 1907 857 1123 246 655 1466 1734 1612 1789 920 1211 614 1448 416 1409 663 759 778 1382 454 1677 1351 1721 1042 1141 1203 1317 587 1066 208 1354 267 345 318 1329 1017 1046 639 1022 1063 1757 345 1008 1261 1700 409 1527 948 1892 1057 1403 168 184 290 1557 1041 1384 1082 1249 1260 1434 1093 1105 47 863 1782 1783 1102 1363 515 624 1261 1585 362 858 402 1858 1139 1341 777 864 967 1577 1659 1786 144 1359 341 1341 510 1869 620 1860 1074 1423 5 1735 934 1713 1212 1606 579 778 188 594 347 1427 1263 1285 693 1038 396 1923 184 320 1098 1757 668 726 54 1848 971 995 726 1282 384 1728 140 1716 975 1844 710 841 980 1100 792 1711 286 946 1212 1305 754 1291 535 1220 1230 1728 606 1110 1511 1578 5 1803 25 554 1193 1898 954 1338 379 1904 693 1654 825 1179 521 1012 239 338 542 729 595 704 1255 1608 530 1665 510 1586 486 982 7 55 629 861 640 836 65 72 240 1027 149 625 486 890 1693 1823 972 1495 47 1876 1011 1406 631 1067 348 518 71 1235 143 971 142 684 326 346 1451 1551 522 1465 83 1639 1528 1871 520 1473 1255 1518 1203 1448 140 906 358 1572 966 1471 715 1695 358 1907 186 778 48 323 173 1869 1148 1307 870 1005 768 1648 787 1616 228 1760 147 517 40 204 887 1845 924 1699 235 1632 501 630 703 1154 1544 1617 1446 1739 328 1843 111 1421 122 173 1194 1195 4 594 725 933 700 1407 449 1834 740 1841 108 1234 521 1246 340 1302 127 856 167 1361 337 348 112 1627 1150 1612 915 1484 461 1308 931 1593 443 1517 803 1802 963 1691 617 1068 1334 1645 1224 1414 262 1012 280 642 260 1673 207 595 34 1927 1621 1704 511 1403 1605 1701 810 1834 537 1213 589 678 1690 1757 863 1470 372 700 517 832 256 1161 658 1902 15 1401 1743 1875 1082 1196 1341 1803 66 1294 1185 1439 665 687 1803 1819 1 1469 824 1350 886 1437 88 1588 1239 1790 1108 1425 182 1280 351 939 1173 1332 805 1310 791 1139 128 714 559 1463 4 1810 723 1876 452 1265 660 1055 904 986 441 461 965 1890 789 1449 553 1830 166 347 1041 1103 1314 1498 597 1803 624 1182 479 1759 8 1369 33 828 1724 1791 460 898 472 1827 975 990 64 586 580 1736 130 1521 72 157 395 1882 89 1141 112 511 766 1879 1593 1734 851 1441 436 1834 10 1427 10 846 817 1502 185 656 217 1312 257 1642 1306 1929 385 998 158 715 1469 1504 1050 1615 986 1668 737 1172 28 210 265 876 1289 1707 110 730 501 1531 669 1099 126 602 709 1596 362 1512 683 715 1306 1561 74 542 248 922 6 1507 1275 1770 216 667 1285 1913 576 930 569 1723 1432 1813 408 1609 950 1870 362 943 397 1735 631 1016 1612 1622 248 1279 356 1477 49 1547 12 1800 504 1551 1675 1835 160 1845 740 1599 465 1174 128 1651 802 1517 102 539 873 1667 161 650 302 1055 170 264 1109 1707 335 1263 102 515 459 1093 376 1327 543 1743 1005 1826 393 1145 177 619 154 1792 787 1093 790 954 1563 1642 369 495 428 504 1017 1688 173 455 360 968 213 461 190 1385 913 1545 740 1444 183 1091 644 949 501 590 402 993 260 1653 663 1307 1311 1655 1434 1682 2 1301 1019 1066 644 1415 562 1812 1501 1875 740 960 837 1601 137 200 194 1656 429 895 554 1133 496 734 1438 1796 965 1352 490 1906 1117 1925 1085 1609 256 881 1126 1456 917 1047 110 1877 774 872 435 1342 1581 1729 208 1283 817 1458 62 1394 32 1670 445 1616 1013 1481 514 1106 1088 1201 944 1231 636 1051 669 886 506 531 343 472 650 1454 889 1383 835 1197 450 1214 1125 1129 1299 1723 251 867 941 975 343 827 781 1926 41 527 840 1475 1134 1575 110 1682 669 1236 1630 1875 597 1177 158 1464 486 879 785 1454 1345 1779 742 1887 836 1331 224 1687 818 1191 713 1715 595 1211 179 356 84 270 115 1418 1083 1286 337 1554 585 1197 215 313 453 1279 377 1823 29 283 720 1006 1708 1895 387 1334 136 1522 1589 1815 351 1053 1137 1584 52 1857 847 1080 36 309 944 1421 47 1853 265 1180 1833 1871 307 1863 2 63 902 1392 1200 1932 367 1195 758 1717 1367 1452 1017 1370 382 1269 728 775 824 1048 401 417 211 1297 525 601 94 1077 309 938 1446 1908 407 907 466 1099 1109 1316 1041 1412 187 835 110 1725 439 1212 1012 1033 458 1283 373 704 514 1237 673 1228 487 1298 704 965 705 1186 52 1645 259 629 229 1530 7 1088 301 444 1603 1834 123 1770 1320 1575 155 919 235 671 1001 1051 725 877 94 1204 852 1664 1529 1661 423 1530 816 1032 525 1232 885 1380 916 1720 351 1870 400 1266 1036 1216 410 616 811 955 274 1118 1320 1530 708 1697 1009 1601 95 822 1194 1550 654 1787 567 706 1059 1489 1235 1402 200 515 1049 1315 961 1509 661 939 466 1927 1116 1690 381 1369 389 1661 1688 1763 85 721 697 1464 105 1668 1128 1246 277 1293 354 1158 119 1197 241 987 604 1682 787 1132 297 1110 798 1090 234 1753 566 1196 67 1532 467 719 548 1471 40 181 361 1281 463 1546 89 1342 545 632 779 1541 1497 1693 2 1584 482 1897 914 1673 628 1924 139 1010 147 406 139 1611 1247 1792 750 1270 1658 1694 1222 1381 173 1703 1150 1664 89 453 1214 1322 1030 1045 338 1681 451 1565 859 1017 482 1790 710 1542 302 1324 618 702 391 951 290 828 425 884 1127 1812 625 1810 523 1021 436 769 529 703 616 1063 1061 1906 836 1702 1032 1120 1226 1631 539 561 1087 1301 530 535 574 1677 158 1026 287 1214 390 492 534 690 927 1428 598 1624 1384 1747 433 796 315 1934 1308 1647 533 998 22 112 1148 1838 540 1188 153 1603 44 362 765 1466 366 1180 1007 1074 235 1304 429 629 162 1682 641 855 620 1473 98 1087 685 1447 62 1252 432 1062 447 1118 755 1527 1317 1652 446 1581 1544 1661 223 1216 151 1078 306 1593 586 780 479 1480 791 1191 555 1351 244 897 1054 1464 448 1072 784 1570 46 1411 955 1653 988 1295 615 825 72 1681 715 787 519 871 422 1927 141 1406 331 1342 1049 1362 168 1384 1003 1524 351 545 1116 1430 203 1155 25 1405 358 814 1262 1657 764 1587 423 958 1113 1211 1546 1737 733 1850 426 629 222 1899 708 1848 60 1326 1063 1229 399 1167 43 1483 24 603 897 1335 1173 1882 956 1398 624 1925 272 1446 99 901 882 1038 1349 1849 1141 1690 625 1848 7 39 13 226 300 814 1286 1559 112 1127 824 1613 354 789 644 1233 106 839 503 846 889 910 692 1086 7 1294 608 1346 838 1253 1277 1316 795 1709 17 1153 132 1677 119 1690 321 492 214 1068 1120 1163 497 1330 233 1439 176 404 503 1753 1127 1789 1308 1684 258 907 46 438 191 1055 281 1460 869 917 205 589 209 1610 1110 1333 483 1274 1044 1726 147 1924 365 1290 786 1150 167 1693 477 1900 88 1545 4 23 286 648 825 1663 1315 1756 112 854 1308 1513 860 1249 16 1880 430 917 278 1888 486 971 199 915 437 1060 1193 1778 102 782 680 1567 20 949 245 1391 720 970 830 1661 264 495 104 1020 920 1785 699 1793 1240 1517 931 1865 634 1137 249 1644 440 641 39 787 205 712 1168 1228 623 698 1499 1682 175 1087 50 1603 693 1530 1244 1599 118 768 1108 1604 1619 1739 698 1473 67 1740 383 1579 735 985 189 1249 1357 1486 1276 1388 599 1513 866 1450 1195 1909 236 1661 1521 1765 483 928 12 717 808 1382 1372 1684 1145 1581 546 1257 689 1883 1238 1434 84 1123 1548 1611 25 1296 964 1050 929 1193 30 1591 168 1288 1080 1251 481 1477 479 1351 868 1864 842 1323 840 1825 896 1547 687 1318 690 1786 1615 1832 1251 1901 828 1466 868 1552 550 1437 459 1564 865 1592 294 888 25 855 1030 1241 1592 1718 779 1110 1402 1478 556 1563 1402 1917 549 1119 503 1657 303 1447 343 1520 836 1452 363 460 127 1284 286 1506 509 1907 9 1014 543 1491 282 568 532 1828 167 330 62 1441 1136 1456 1084 1557 426 652 813 1445 571 905 1265 1834 291 1285 85 617 31 1287 601 649 354 1108 253 1793 449 1552 1568 1891 771 1031 297 1666 1047 1594 1012 1701 30 930 222 774 530 1611 275 683 1200 1824 34 305 200 1496 284 1305 437 1791 1211 1290 206 1221 303 1027 121 1780 954 1742 79 519 549 814 1397 1856 329 1742 1161 1459 1381 1608 375 446 1181 1696 1408 1548 580 1099 16 1808 452 1344 52 449 715 1603 420 1565 796 1567 237 1331 588 1698 26 197 493 694 103 272 432 583 703 1256 711 1615 80 134 558 1800 260 1866 928 1135 600 1066 1225 1778 1300 1407 23 1357 1157 1584 268 848 1151 1898 119 1068 122 1187 774 1137 122 1767 1074 1478 371 1476 454 1801 70 1783 773 1720 833 1444 289 345 798 1448 2 47 960 1546 371 1595 1446 1742 371 1780 559 954 81 1677 618 1555 261 589 283 606 547 1612 67 489 541 1548 572 1609 1592 1690 1094 1660 484 1454 1315 1507 1053 1758 940 1127 655 1308 145 1772 849 1497 624 1576 1031 1198 100 800 149 553 170 524 625 626 9 1582 346 1372 351 1413 163 1113 752 960 27 677 386 393 293 1638 144 787 1706 1881 1408 1522 858 1319 534 1669 235 1048 1639 1815 716 1834 537 1442 1191 1602 577 1527 1271 1770 1441 1831 496 1684 370 1246 1029 1873 242 1252 499 1765 266 1194 1015 1754 119 501 701 878 1799 1826 1429 1740 230 279 268 637 529 1211 150 1840 232 852 345 572 684 1031 124 1462 56 1865 1646 1814 663 1393 618 1811 107 1285 1108 1781 1323 1382 82 202 110 728 221 351 174 555 206 1131 382 1445 290 1931 407 457 1010 1440 459 1590 393 1170 1100 1638 659 1925 1455 1920 177 327 265 1124 269 1231 285 485 675 1381 696 1603 1639 1759 349 412 917 1798 261 1104 507 794 34 1861 1047 1897 119 1111 602 1740 227 1300 613 1062 1019 1398 1626 1641 739 1511 10 534 1175 1740 441 1435 78 883 1314 1766 265 1016 42 1367 208 1165 917 1784 1268 1502 380 1667 334 1899 1062 1712 131 976 542 1625 296 1514 776 1910 825 1883 582 1251 144 983 629 1716 780 1082 605 970 1382 1654 989 1346 369 756 147 254 589 1351 595 629 953 1446 1173 1852 192 1850 28 413 1523 1779 954 1093 135 1870 1453 1865 202 867 229 279 457 1580 381 1461 1427 1566 295 729 10 1093 277 1092 487 1036 809 1314 533 565 402 1562 560 712 212 1462 625 672 267 1850 925 1743 319 1065 1273 1596 119 1539 668 1062 255 998 258 1598 931 1474 829 1778 825 1250 1235 1469 263 1777 84 1723 824 1705 36 746 839 1505 668 695 1340 1456 419 1850 1593 1894 374 1345 508 1448 874 1007 200 1667 820 1825 1386 1804 1065 1205 11 1177 938 1761 884 942 53 1843 351 1224 605 1847 478 1624 185 1354 118 1631 189 901 887 1215 2 1074 273 1489 1092 1682 109 1007 1234 1835 121 176 1309 1646 348 1454 117 1131 1310 1735 745 1382 662 1640 817 1777 450 1400 701 1674 1569 1616 510 1410 1025 1895 26 244 139 757 894 1100 258 1765 571 1131 320 826 742 1219 14 109 143 1694 823 981 1623 1786 580 681 862 1396 878 1409 1046 1292 1011 1346 394 1682 781 1693 292 1100 898 1456 1654 1685 573 1763 510 1162 309 369 1295 1601 1785 1884 110 1064 688 1180 423 1178 486 1849 364 1816 1076 1462 1264 1849 369 898 46 1551 338 992 1818 1912 564 598 676 1203 211 916 86 1439 459 1510 120 772 254 1300 2 1537 139 470 1767 1922 89 1482 110 1106 737 1320 960 1110 22 1597 629 996 46 767 287 1762 800 1441 429 1873 834 1320 195 1560 301 1678 246 793 1283 1395 738 1485 119 1278 119 1176 129 1102 36 1558 418 1309 573 1905 796 1181 1756 1895 722 1479 839 853 361 502 511 1713 276 1197 47 596 1614 1643 314 669 746 1918 536 753 1527 1530 1163 1200 594 664 1489 1789 247 1249 603 1348 308 1812 803 1709 148 574 943 1160 203 1369 1296 1347 528 1524 724 730 663 1062 897 1258 362 708 148 711 139 1545 85 1574 235 1713
Output: 16

Constraints:

1 <= n <= 1973; 0 <= m <= 3946.

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