CT52510

The Circular Route Beneath Saprun

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Gardener runs the kiln at the maple sugarbush of Saprun. Today the books show a list of roads, and the numbers must be worked out before sundown. 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 <= 3587; 0 <= m <= 3587.

Example 1:

Input: 3335 746 3073 187 1364 3003 3216 2158 1881 2967 2885 2123 921 927 2330 2193 2081 809 2397 1652 937 3218 2257 1051 174 1804 2799 2519 3233 2729 2066 3121 415 157 1669 1656 1105 2122 2157 1979 298 1384 248 2337 1809 2614 558 1792 1137 2983 1435 2680 1953 2171 1889 678 1366 2140 2576 1653 2213 1892 1116 630 538 1456 365 921 2019 2040 809 2908 2621 2454 1949 1991 529 166 1014 1768 1671 2175 2012 1426 1542 2188 625 451 3114 2912 1058 827 975 386 1878 1271 671 2874 1328 2853 918 1287 1113 324 2863 3195 1158 2264 3050 2534 1715 1353 1513 586 244 2062 465 567 314 2318 289 1625 1808 2898 2940 362 3295 15 296 2335 2778 1126 1670 1061 1319 1971 1967 3267 2908 1421 829 239 836 2259 2112 1766 2291 1042 1792 2966 2861 1348 912 1186 555 2989 1884 916 2409 1629 2152 1694 2015 1236 1166 3328 1425 2209 3034…
Output: NO

Example 2:

Input: 2720 391 108 44 423 2112 1098 2229 820 2701 635 2376 684 273 2494 70 538 31 1600 2172 1205 1629 2067 100 917 738 296 748 2470 1573 1439 9 1117 1 1602 2378 2117 1196 643 1440 983 1993 1054 355 1879 1484 1229 95 1617 791 1901 1974 1639 2408 962 2135 1940 251 1446 2567 263 117 1951 27 1522 2398 1420 1162 856 1000 713 2674 2208 790 233 1106 656 1817 1528 2213 963 310 1589 2079 2487 2215 648 1648 189 2517 233 415 850 395 888 525 2368 2101 1359 2659 1742 1389 1388 1685 1749 410 2645 878 1834 20 922 2707 1180 480 954 1836 368 864 464 1395 2093 1704 515 2495 1282 420 1329 1354 1487 1078 1772 2196 528 1568 2044 2048 471 188 2398 405 554 1713 1832 2591 1709 2233 1450 490 2176 423 1772 2292 242 2575 1468 1646 1975 2490 2334 84 497 206 1361 1573 1127 1353 1308 772 1505 2312 2211 1501 1951 1375 172 254…
Output: NO

Example 3:

Input: 605 3174 252 63 98 540 133 314 390 173 397 417 396 19 83 323 251 446 383 403 276 548 482 421 439 242 242 261 286 223 270 592 400 39 255 308 263 137 170 482 37 333 173 421 162 307 96 466 358 461 335 176 439 251 365 484 93 505 360 505 528 340 262 119 548 83 258 128 368 429 271 172 532 424 248 98 489 403 509 380 572 385 47 104 185 580 172 167 207 588 345 498 281 517 201 589 485 137 560 574 114 273 75 440 255 390 414 473 60 102 229 484 489 281 56 410 488 259 590 20 201 417 594 493 138 158 396 399 480 397 96 514 447 352 342 594 209 334 509 514 536 154 357 467 242 11 244 99 154 380 3 42 374 280 382 372 500 370 21 360 85 174 394 528 30 459 117 509 136 27 161 139 271 381 437 408 194 220 78 556 141 392 553 308 382 65 117 433 592 431 248 257 489 97 113 375 522 406 261 472 521 154 440 422 213 62 417 …
Output: YES

Constraints:

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

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