CT46104

Sailor's Crystal tunnels

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Sailor inherited the gallery at the ember mines of Cindercrag along with its curious bookkeeping system for tunnels. Time to make sense of it. Task: Print YES if the directed graph contains a cycle, otherwise NO. Input format: First line: n and m. Next m lines: u v (directed). Output format: Print YES or NO. Constraints: 1 <= n <= 3439; 0 <= m <= 3439.

Example 1:

Input: 1546 981 265 1423 556 304 1229 1321 704 488 402 832 816 197 1271 462 1016 1053 1054 1295 1435 901 216 1172 1511 1288 295 986 524 603 1290 161 433 1346 1226 1213 1213 1240 1117 284 969 15 867 1088 537 1430 898 358 110 869 1354 1230 712 195 1505 701 4 396 616 182 248 38 586 702 322 1005 439 116 1025 805 31 816 516 328 1275 896 150 1297 96 1032 708 92 1266 1238 124 793 864 107 1494 1196 842 1356 563 537 890 1455 680 515 191 203 995 1508 743 254 1242 953 1463 685 136 712 143 1411 136 879 207 866 1163 437 969 1270 134 346 351 584 403 827 1302 963 1285 772 423 1086 1313 412 1157 1436 1176 368 1409 881 635 1407 692 120 746 560 1164 1450 91 497 1381 319 769 173 802 934 266 1299 1204 679 990 706 1391 273 37 192 114 73 756 367 1321 1407 789 1226 743 818 1523 349 733 1217 1262 1253 1119 1395 1543 619…
Output: NO

Example 2:

Input: 3252 1454 1964 3005 1086 2540 767 2341 514 2935 2073 2981 1266 1223 3081 1951 672 637 2938 480 1726 1342 644 442 453 1485 125 3022 793 365 2273 1184 1923 536 448 2066 3039 2411 1796 362 660 2705 1005 1078 3103 3059 2248 2680 1596 947 3162 1747 805 1757 2772 1642 2374 1718 1401 2830 1436 1070 596 1135 1046 1807 1066 1535 2332 2350 3202 2431 1443 2549 3090 127 520 2511 1229 1156 2743 1995 2809 2486 1362 964 2487 1580 2153 2760 2398 3207 2754 1040 2639 739 1865 3121 316 678 142 2408 1928 2282 1086 241 247 836 1924 1227 555 2956 1441 1299 2195 2606 653 2045 3015 1294 2216 3037 114 1731 25 1267 59 3165 174 2834 2949 1894 1871 60 2943 614 651 2138 417 2059 697 380 108 1079 1523 679 740 1474 1995 1612 2494 2368 740 1436 936 1288 2550 1207 2323 2143 89 1239 176 3170 2810 689 2294 144 2481 614 2904…
Output: NO

Example 3:

Input: 3076 682 3031 188 2015 1396 3055 707 1729 549 1038 2657 1712 1798 108 1685 277 1194 395 2041 2756 2051 443 1503 2334 604 1880 1012 973 3062 543 989 2950 2383 731 1880 3021 2639 694 717 448 421 764 2152 2235 462 1677 507 178 2196 1779 803 1904 1758 2137 351 93 1446 2608 859 2559 1246 331 1848 1396 331 18 439 1919 224 2416 1322 706 356 2534 3012 2235 1230 76 563 477 2277 2369 973 2055 2104 1467 491 1048 1939 1382 142 2889 2449 2974 1297 1674 2266 674 2933 1682 2798 2302 2873 661 406 524 2684 3063 552 2480 702 2624 1140 2970 1191 2479 3050 1890 1003 694 1626 611 789 2109 2998 575 213 6 2611 88 872 516 92 2910 1113 1472 2463 619 1310 164 2787 1036 2468 769 2672 2451 1417 2176 772 683 2952 1668 2066 1129 2070 3036 1975 294 2120 1850 7 1499 2376 529 2755 2272 2439 2098 2545 2726 3002 225 1427 13…
Output: NO

Constraints:

1 <= n <= 3439; 0 <= m <= 3439.

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