CT41508

The tunnels at Horselord Plains

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Lara found an old ledger of tunnels in the ferry office attic at the steppe camp of Horselord Plains. The margin notes pose a precise question. 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 <= 2762; 0 <= m <= 2762.

Example 1:

Input: 2269 1446 785 1563 1763 1664 294 1596 1129 353 2019 252 771 1007 503 414 1449 808 136 455 1084 1203 462 257 461 1356 2262 1029 1134 1918 17 297 1206 1144 789 468 1590 728 47 168 2142 1982 2204 278 2035 1829 2038 623 1140 1721 2175 57 240 801 2144 1368 1415 1903 362 2175 1898 825 814 332 1012 1772 961 1540 1976 759 667 971 212 487 320 1763 1156 646 623 148 125 714 1842 499 1542 2195 351 30 1935 2260 1960 1499 2015 2083 912 53 2115 464 1766 1905 508 1613 1768 477 2202 1146 303 361 1867 2259 195 250 1378 1667 1049 1800 476 225 1123 1413 1448 243 794 2110 777 2073 1810 688 590 1956 1293 1565 1467 1138 1759 2229 1470 1807 1350 1334 1271 59 983 1565 966 63 877 585 984 1272 1086 2246 305 497 312 314 1789 1254 1768 1125 466 226 1370 2179 2039 454 707 1191 1144 2228 1068 701 1250 1769 1015 1263 207…
Output: NO

Example 2:

Input: 1035 1200 746 507 759 189 897 447 282 883 685 404 245 129 992 622 980 656 485 886 544 154 545 907 278 888 196 108 997 471 611 707 545 58 925 632 129 840 264 360 289 663 813 431 462 631 554 1006 277 709 504 960 50 147 49 376 613 39 867 245 993 804 435 822 800 874 903 727 216 82 458 444 784 136 716 248 46 799 961 572 304 528 91 701 431 793 516 827 650 986 330 626 652 327 123 328 837 18 304 550 801 457 590 402 820 560 608 716 448 873 665 250 766 1026 132 850 915 117 198 1007 585 236 126 596 89 57 591 863 343 466 603 121 899 122 71 170 408 569 242 483 54 22 473 628 865 44 863 475 857 70 970 98 21 201 451 1001 918 691 910 631 160 172 381 4 633 328 895 216 254 766 426 894 353 868 636 917 881 215 52 649 551 154 452 863 61 281 95 807 320 604 696 952 423 405 376 263 752 681 991 566 340 404 961 147 …
Output: YES

Example 3:

Input: 1830 68 1790 1388 870 839 1333 305 539 924 1111 293 725 1501 1332 19 1063 1568 1030 734 1039 1753 312 1622 1137 1250 744 1221 717 196 1664 1093 1 646 1159 865 297 157 1361 1290 1532 1810 875 773 1447 527 1238 1248 284 788 116 854 189 12 1206 711 616 1449 1687 772 588 209 974 1677 1087 807 1218 852 1630 937 500 1698 1019 700 1344 972 282 883 47 1456 1735 406 22 965 1757 834 1566 408 1523 1479 378 252 1635 913 24 675 929 1771 989 84 1612 796 1384 1771 1472 427 1611 1424 729 416 590 1293 1640 1265 1356 1760 287 384 1451 723 1242 476 1256 1757 1398 1492 1581 1447 1583 1087 1442 429 147 697 977 1707 1830 1
Output: NO

Constraints:

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

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