CT39220

Zia's Circular Route Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the zephyr cliffs of Galeholm, someone must map a faster supply route. This year the task falls to Zia, armed only with the bridges register. 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 <= 3536; 0 <= m <= 3536.

Example 1:

Input: 3430 802 2969 1624 869 999 3199 2097 1109 1630 351 2896 1448 2496 3037 1069 1792 2726 3267 1590 3333 2613 1907 1749 89 2911 658 3242 3140 2288 741 1663 2391 915 2068 3042 2130 2345 1421 3350 3206 2712 301 2662 1034 704 1498 3319 1600 80 1219 3182 1961 2061 428 780 2494 3139 1823 3337 1871 1192 2375 908 895 3309 1623 781 3280 2505 2461 2270 1927 23 854 989 815 2797 850 4 1993 2199 1308 1587 754 2049 410 1657 1926 2713 3209 1471 1656 366 3242 2056 232 850 1453 3274 820 2337 929 1905 101 741 1313 2046 1380 3378 1992 2869 1572 2092 1469 1049 2584 347 3044 2796 1649 3114 694 2593 2633 612 717 2361 448 3179 1013 1714 1827 2535 1535 1874 601 3345 737 2371 45 444 2575 2576 874 73 140 424 2745 3319 1635 1726 1443 1910 1486 720 2216 942 1950 485 1412 1249 1406 2553 3085 984 231 731 1259 3357 3 1451 …
Output: NO

Example 2:

Input: 2238 2261 508 2193 20 1780 120 515 271 1830 1071 186 1429 1478 1786 2050 1823 301 1805 1409 976 447 460 916 1603 2211 1523 1221 1189 1488 1708 1986 1650 1163 1580 150 80 1638 1351 333 1215 1281 1236 851 1173 270 473 1024 1012 1674 1357 360 914 1415 1364 1462 383 1736 1679 1940 288 628 2075 1701 1894 793 306 677 1501 2204 1946 27 2109 1332 1578 738 640 425 248 942 1075 1146 1724 1292 2157 970 771 1724 906 1509 696 779 1579 1337 718 51 806 340 700 648 324 1992 1053 1252 1257 1387 1838 753 765 501 1242 690 699 2172 2008 1216 1517 1185 299 1475 294 1591 979 2083 2010 1340 2152 865 411 57 36 985 796 1882 718 1133 1747 1691 434 1367 1002 1887 392 1902 1125 561 1304 2230 245 1696 21 944 1582 1103 1019 1598 1386 504 1048 1564 506 988 1695 1359 1886 1438 2079 1843 805 1242 1492 1241 773 1560 1668 8…
Output: YES

Example 3:

Input: 1661 3279 665 1332 995 1192 492 1549 122 595 959 1084 25 686 1062 1615 1393 421 1542 1511 1285 100 926 1558 274 148 856 630 128 582 170 1089 1380 450 1646 891 440 311 293 274 1129 346 1554 58 317 1151 1156 481 1025 1207 1647 858 1655 156 75 447 1095 428 267 1318 1472 1374 1164 1375 733 892 392 306 735 638 350 1586 1565 1584 1345 560 913 301 1231 1656 942 1061 1448 578 1569 464 1363 1197 97 332 778 1496 882 60 672 450 198 1228 1292 750 1347 1071 1327 1000 282 485 1155 900 722 1531 1418 1376 402 1522 310 253 511 158 750 471 910 514 1304 1363 1178 1191 1655 1282 780 858 499 560 116 818 738 180 1324 14 573 416 512 1134 932 1578 384 279 528 757 884 643 1470 329 1615 214 139 978 167 435 933 820 1013 41 36 1170 674 566 274 1042 407 1112 596 340 789 178 804 700 811 1486 1093 426 237 1052 675 828 6…
Output: YES

Constraints:

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

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