CT40733

The Opal canals of Wynne

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Wynne the surveyor watches over the ember mines of Cindercrag's stores of canals. A careful computation stands between order and chaos. 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 <= 1670; 0 <= m <= 1670.

Example 1:

Input: 1272 1034 431 1170 407 178 902 866 1225 828 1111 1138 514 158 816 1031 515 783 485 524 843 361 270 690 299 417 735 662 1205 529 140 147 559 980 334 883 737 394 669 215 588 995 394 1009 1151 977 973 519 310 438 741 956 866 31 160 207 450 859 54 429 21 90 662 489 31 538 616 305 1260 1236 1032 1108 1091 1061 444 243 371 1207 812 459 826 333 987 312 888 205 656 189 261 782 268 131 594 216 136 1135 965 585 579 1004 760 405 952 382 1270 688 1015 1162 942 720 1187 616 1037 1021 970 365 251 876 437 602 917 294 1229 274 1058 664 78 119 577 349 845 218 1011 972 854 1082 1091 626 717 370 1112 517 8 1047 1171 402 823 108 1034 847 648 922 556 1044 1206 960 5 431 919 143 352 1243 190 389 335 495 503 1249 496 743 775 526 1003 263 770 526 833 86 45 869 466 1095 1189 1018 474 423 557 780 560 891 446 78 109…
Output: NO

Example 2:

Input: 832 1080 548 661 556 356 570 499 336 612 261 719 654 773 604 516 126 65 414 730 816 820 392 799 432 230 247 464 153 160 119 283 200 185 373 493 805 70 312 298 391 141 21 139 632 278 213 456 337 124 145 545 29 608 282 274 629 683 590 523 251 466 501 128 375 156 374 302 625 718 742 793 333 1 634 428 743 447 238 179 359 388 228 823 272 788 20 433 724 112 98 228 350 458 626 765 425 391 697 616 419 666 159 29 820 383 285 5 679 295 313 82 516 736 762 786 491 577 165 267 365 589 538 284 147 105 572 553 641 780 51 781 299 545 781 145 134 778 483 562 643 640 618 76 511 396 171 623 703 323 362 722 229 767 388 809 738 388 32 81 403 768 559 595 318 224 548 710 565 749 428 389 451 431 717 538 654 18 549 788 545 159 818 305 677 152 636 563 773 35 200 8 59 533 485 92 48 775 323 170 781 520 599 766 208 21…
Output: YES

Example 3:

Input: 1025 699 587 296 84 67 52 599 831 474 575 498 1011 780 29 255 373 807 539 315 950 601 473 403 467 5 690 225 775 665 645 512 289 950 750 22 645 177 420 1020 980 159 1008 715 96 711 752 58 644 888 918 665 524 595 327 381 7 228 318 901 870 694 964 572 824 297 286 734 618 661 977 34 566 888 18 126 776 271 116 573 594 963 828 600 651 484 451 765 580 626 378 513 342 203 892 143 719 168 708 695 153 704 4 986 812 417 264 225 249 451 822 14 156 581 318 740 843 671 824 1019 581 717 61 271 124 674 635 962 743 111 948 867 77 49 334 412 743 302 415 417 482 750 807 333 900 23 854 449 146 231 952 987 519 452 661 996 862 528 498 645 236 365 561 41 521 478 979 646 387 945 993 869 680 905 178 351 780 304 444 497 970 101 795 957 207 441 399 323 34 434 177 370 134 886 1009 519 188 732 371 780 658 112 516 806 …
Output: YES

Constraints:

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

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