FPEvalDataset/LeetCodeProblem
0304
1{2 "id": 2671,3 "name": "shortest_cycle_in_a_graph",4 "difficulty": "Hard",5 "link": "https://leetcode.com/problems/shortest-cycle-in-a-graph/",6 "date": "1679097600000",7 "task_description": "There is a **bi-directional **graph with `n` vertices, where each vertex is labeled from `0` to `n - 1`. The edges in the graph are represented by a given 2D integer array `edges`, where `edges[i] = [ui, vi]` denotes an edge between vertex `ui` and vertex `vi`. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself. Return _the length of the **shortest **cycle in the graph_. If no cycle exists, return `-1`. A cycle is a path that starts and ends at the same node, and each edge in the path is used only once. **Example 1:** ``` **Input:** n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]] **Output:** 3 **Explanation:** The cycle with the smallest length is : 0 -> 1 -> 2 -> 0 ``` **Example 2:** ``` **Input:** n = 4, edges = [[0,1],[0,2]] **Output:** -1 **Explanation:** There are no cycles in this graph. ``` **Constraints:** `2 <= n <= 1000` `1 <= edges.length <= 1000` `edges[i].length == 2` `0 <= ui, vi < n` `ui != vi` There are no repeated edges.",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]]",12 "output": "3 "13 },14 {15 "label": "Example 2",16 "input": "n = 4, edges = [[0,1],[0,2]]",17 "output": "-1 "18 }19 ],20 "private_test_cases": [21 {22 "input": [23 954,24 [25 [26 266,27 92428 ],29 [30 501,31 82732 ],33 [34 75,35 39936 ],37 [38 103,39 15240 ],41 [42 183,43 27044 ],45 [46 187,47 88748 ],49 [50 445,51 74652 ],53 [54 405,55 71056 ],57 [58 792,59 89060 ],61 [62 82,63 70364 ],65 [66 175,67 27568 ],69 [70 403,71 75872 ],73 [74 572,75 72576 ],77 [78 346,79 66080 ],81 [82 37,83 16184 ],85 [86 388,87 48688 ],89 [90 497,91 82992 ],93 [94 538,95 83096 ],97 [98 339,99 355100 ],101 [102 484,103 621104 ],105 [106 620,107 643108 ],109 [110 130,111 218112 ],113 [114 512,115 948116 ],117 [118 178,119 276120 ],121 [122 271,123 742124 ],125 [126 197,127 289128 ],129 [130 491,131 507132 ],133 [134 15,135 398136 ],137 [138 14,139 15140 ],141 [142 320,143 625144 ],145 [146 104,147 583148 ],149 [150 123,151 834152 ],153 [154 400,155 743156 ],157 [158 562,159 814160 ],161 [162 3,163 33164 ],165 [166 144,167 399168 ],169 [170 627,171 880172 ],173 [174 297,175 498176 ],177 [178 710,179 905180 ],181 [182 31,183 607184 ],185 [186 573,187 661188 ],189 [190 125,191 669192 ],193 [194 85,195 178196 ],197 [198 562,199 926200 ],201 [202 81,203 473204 ],205 [206 285,207 361208 ],209 [210 411,211 775212 ],213 [214 139,215 414216 ],217 [218 368,219 423220 ],221 [222 675,223 821224 ],225 [226 97,227 844228 ],229 [230 130,231 878232 ],233 [234 221,235 242236 ],237 [238 71,239 801240 ],241 [242 147,243 921244 ],245 [246 378,247 952248 ],249 [250 127,251 305252 ],253 [254 563,255 625256 ],257 [258 55,259 685260 ],261 [262 518,263 721264 ],265 [266 127,267 323268 ],269 [270 304,271 770272 ],273 [274 486,275 670276 ],277 [278 77,279 462280 ],281 [282 53,283 541284 ],285 [286 66,287 560288 ],289 [290 84,291 129292 ],293 [294 231,295 291296 ],297 [298 342,299 891300 ],301 [302 56,303 775304 ],305 [306 861,307 943308 ],309 [310 187,311 877312 ],313 [314 876,315 941316 ],317 [318 90,319 270320 ],321 [322 71,323 693324 ],325 [326 98,327 521328 ],329 [330 456,331 894332 ],333 [334 549,335 555336 ],337 [338 616,339 883340 ],341 [342 349,343 768344 ],345 [346 508,347 694348 ],349 [350 221,351 619352 ],353 [354 202,355 767356 ],357 [358 60,359 912360 ],361 [362 84,363 879364 ],365 [366 583,367 953368 ],369 [370 418,371 895372 ],373 [374 33,375 913376 ],377 [378 166,379 292380 ],381 [382 400,383 468384 ],385 [386 19,387 102388 ],389 [390 115,391 326392 ],393 [394 243,395 484396 ],397 [398 55,399 424400 ],401 [402 110,403 787404 ],405 [406 170,407 271408 ],409 [410 490,411 779412 ],413 [414 302,415 948416 ],417 [418 423,419 680420 ],421 [422 125,423 367424 ],425 [426 239,427 779428 ],429 [430 56,431 258432 ],433 [434 76,435 236436 ],437 [438 457,439 849440 ],441 [442 366,443 740444 ],445 [446 560,447 871448 ],449 [450 81,451 598452 ],453 [454 567,455 739456 ],457 [458 258,459 896460 ],461 [462 764,463 866464 ],465 [466 444,467 897468 ],469 [470 28,471 461472 ],473 [474 289,475 883476 ],477 [478 50,479 458480 ],481 [482 371,483 791484 ],485 [486 227,487 926488 ],489 [490 153,491 321492 ],493 [494 139,495 148496 ],497 [498 57,499 771500 ],501 [502 241,503 690504 ],505 [506 138,507 189508 ],509 [510 351,511 571512 ],513 [514 252,515 848516 ],517 [518 405,519 560520 ],521 [522 269,523 361524 ],525 [526 159,527 904528 ],529 [530 180,531 698532 ],533 [534 386,535 528536 ],537 [538 36,539 406540 ],541 [542 779,543 877544 ],545 [546 201,547 748548 ],549 [550 333,551 391552 ],553 [554 46,555 874556 ],557 [558 523,559 533560 ],561 [562 235,563 395564 ],565 [566 611,567 893568 ],569 [570 367,571 551572 ],573 [574 37,575 914576 ],577 [578 147,579 529580 ],581 [582 13,583 953584 ],585 [586 2,587 538588 ],589 [590 20,591 583592 ],593 [594 820,595 923596 ],597 [598 593,599 881600 ],601 [602 124,603 393604 ],605 [606 157,607 161608 ],609 [610 71,611 256612 ],613 [614 198,615 449616 ],617 [618 481,619 639620 ],621 [622 412,623 576624 ],625 [626 823,627 952628 ],629 [630 203,631 393632 ],633 [634 137,635 228636 ],637 [638 387,639 650640 ],641 [642 162,643 788644 ],645 [646 218,647 710648 ],649 [650 542,651 798652 ],653 [654 190,655 230656 ],657 [658 267,659 679660 ],661 [662 229,663 814664 ],665 [666 37,667 235668 ],669 [670 430,671 575672 ],673 [674 352,675 637676 ],677 [678 131,679 827680 ],681 [682 334,683 598684 ],685 [686 13,687 45688 ],689 [690 685,691 703692 ],693 [694 128,695 520696 ],697 [698 298,699 931700 ],701 [702 537,703 548704 ],705 [706 530,707 936708 ],709 [710 329,711 528712 ],713 [714 356,715 783716 ],717 [718 876,719 926720 ],721 [722 823,723 920724 ],725 [726 135,727 406728 ],729 [730 334,731 881732 ],733 [734 616,735 868736 ],737 [738 742,739 855740 ],741 [742 172,743 553744 ],745 [746 213,747 600748 ],749 [750 427,751 672752 ],753 [754 174,755 263756 ],757 [758 561,759 761760 ],761 [762 19,763 716764 ],765 [766 819,767 904768 ],769 [770 29,771 281772 ],773 [774 158,775 502776 ],777 [778 379,779 897780 ],781 [782 11,783 74784 ],785 [786 5,787 570788 ],789 [790 355,791 787792 ],793 [794 281,795 572796 ],797 [798 96,799 456800 ],801 [802 757,803 928804 ],805 [806 477,807 794808 ],809 [810 403,811 854812 ],813 [814 24,815 31816 ],817 [818 349,819 883820 ],821 [822 30,823 352824 ],825 [826 433,827 715828 ],829 [830 112,831 153832 ],833 [834 199,835 557836 ],837 [838 841,839 927840 ],841 [842 155,843 380844 ],845 [846 556,847 822848 ],849 [850 29,851 402852 ],853 [854 218,855 817856 ],857 [858 608,859 832860 ],861 [862 343,863 934864 ],865 [866 389,867 812868 ],869 [870 384,871 468872 ],873 [874 447,875 744876 ],877 [878 274,879 834880 ],881 [882 576,883 638884 ],885 [886 428,887 474888 ],889 [890 7,891 728892 ],893 [894 134,895 549896 ],897 [898 91,899 718900 ],901 [902 224,903 851904 ],905 [906 143,907 261908 ],909 [910 383,911 597912 ],913 [914 724,915 899916 ],917 [918 302,919 919920 ],921 [922 164,923 311924 ],925 [926 535,927 749928 ],929 [930 610,931 752932 ],933 [934 301,935 582936 ],937 [938 46,939 441940 ],941 [942 584,943 870944 ],945 [946 222,947 508948 ],949 [950 199,951 552952 ],953 [954 146,955 635956 ],957 [958 125,959 185960 ],961 [962 390,963 757964 ],965 [966 895,967 920968 ],969 [970 76,971 728972 ],973 [974 592,975 730976 ],977 [978 897,979 948980 ],981 [982 143,983 876984 ],985 [986 25,987 372988 ],989 [990 257,991 907992 ],993 [994 431,995 803996 ],997 [998 417,999 4961000 ],1001 [1002 616,1003 9341004 ],1005 [1006 109,1007 6271008 ],1009 [1010 245,1011 7981012 ],1013 [1014 806,1015 9421016 ],1017 [1018 618,1019 7421020 ],1021 [1022 56,1023 2151024 ],1025 [1026 31,1027 2801028 ],1029 [1030 92,1031 1471032 ],1033 [1034 84,1035 9481036 ],1037 [1038 61,1039 5681040 ],1041 [1042 200,1043 4851044 ],1045 [1046 161,1047 8931048 ],1049 [1050 487,1051 6851052 ],1053 [1054 78,1055 4861056 ],1057 [1058 853,1059 8911060 ],1061 [1062 566,1063 5691064 ],1065 [1066 260,1067 6241068 ],1069 [1070 841,1071 9351072 ],1073 [1074 91,1075 8521076 ],1077 [1078 665,1079 7001080 ],1081 [1082 626,1083 6291084 ],1085 [1086 596,1087 8661088 ],1089 [1090 226,1091 2501092 ],1093 [1094 388,1095 4101096 ],1097 [1098 473,1099 7771100 ],1101 [1102 86,1103 5171104 ],1105 [1106 158,1107 8601108 ],1109 [1110 55,1111 2731112 ],1113 [1114 735,1115 7921116 ],1117 [1118 10,1119 6251120 ],1121 [1122 116,1123 6431124 ],1125 [1126 506,1127 8101128 ],1129 [1130 144,1131 2961132 ],1133 [1134 135,1135 2381136 ],1137 [1138 108,1139 2211140 ],1141 [1142 78,1143 3691144 ],1145 [1146 184,1147 6161148 ],1149 [1150 454,1151 8671152 ],1153 [1154 69,1155 5491156 ],1157 [1158 54,1159 2681160 ],1161 [1162 276,1163 6281164 ],1165 [1166 521,1167 5661168 ],1169 [1170 210,1171 5151172 ],1173 [1174 549,1175 6461176 ],1177 [1178 358,1179 6881180 ],1181 [1182 229,1183 3761184 ],1185 [1186 341,1187 8551188 ],1189 [1190 505,1191 7071192 ],1193 [1194 214,1195 6431196 ],1197 [1198 14,1199 4781200 ],