CT46156

The Circular Route of Tranquil Basin

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the lotus ponds of Tranquil Basin. Vani spreads the routes records across the table and picks up a sharp pencil. 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 <= 1996; 0 <= m <= 1996.

Example 1:

Input: 1841 1235 446 1835 1113 1822 540 914 722 1140 1443 1437 868 651 1572 210 1525 22 926 723 1382 985 1190 1714 1581 1577 1227 1331 162 552 169 387 338 461 316 172 1782 1625 137 368 731 1624 595 573 369 1277 1490 661 1261 1689 423 1498 1049 176 1757 776 491 1536 1391 323 1187 598 457 1768 120 784 880 839 520 1222 1146 733 1160 362 727 976 129 407 1472 757 1328 1610 406 810 1075 1273 316 1419 1807 959 1274 1294 1583 1603 948 989 374 353 232 1551 638 1218 441 1814 1193 614 1243 1225 806 363 1311 1671 1688 380 1138 707 51 694 969 1281 927 915 169 1063 1199 1811 972 869 742 499 141 51 1614 645 895 1199 1532 315 1046 1512 1007 993 780 313 864 417 1555 780 413 1224 1097 1810 1739 1520 1083 248 10 417 1363 664 760 1084 305 1624 717 277 1138 1542 1267 1520 724 1188 1786 732 488 984 1093 1107 740 1537 …
Output: YES

Example 2:

Input: 120 1014 103 4 29 81 112 26 3 21 42 54 25 21 89 59 67 58 69 28 44 111 55 107 87 36 74 119 96 116 51 112 47 67 118 85 55 105 63 8 31 76 8 115 86 13 74 108 81 43 101 20 47 95 45 30 66 30 42 97 92 33 112 20 114 111 62 29 103 11 23 106 49 19 73 11 16 44 93 2 15 37 42 17 6 56 11 81 110 35 87 105 105 117 49 105 25 90 4 12 48 71 106 67 110 18 63 7 64 114 28 84 36 2 53 103 76 22 97 40 93 104 13 34 14 108 100 35 62 86 57 74 27 74 7 25 41 20 94 17 89 106 65 54 25 70 106 40 64 6 13 99 11 55 89 96 5 4 22 97 103 24 50 73 4 78 74 57 38 45 60 55 119 33 10 106 26 114 69 117 64 19 101 106 25 24 119 115 57 43 71 57 78 81 90 70 94 104 29 118 74 42 51 90 37 19 88 80 81 74 120 97 107 99 120 55 42 82 76 109 51 83 42 72 36 20 87 44 71 6 34 16 68 114 1 110 79 97 111 60 80 50 7 84 23 37 73 67 114 55 97 115 44 107 …
Output: YES

Example 3:

Input: 1432 790 224 1237 219 317 1130 207 747 48 767 919 1190 1003 679 519 1328 407 915 227 798 941 934 571 1171 578 1016 1077 263 463 656 1004 1304 1107 551 1144 894 545 760 1420 729 723 387 318 426 1008 218 141 1286 362 469 930 9 544 1351 1007 320 95 678 663 728 1302 466 1161 1166 70 1165 70 1162 61 1357 1005 1141 259 963 831 466 820 1216 978 1404 160 950 178 115 1258 277 964 1125 425 529 130 998 1263 558 1347 589 914 279 596 40 1373 1001 1382 1083 43 1082 311 333 305 30 1255 141 341 1334 806 531 563 1100 1131 344 46 192 912 770 233 1031 937 609 981 769 47 1387 1261 1236 414 598 219 189 1081 898 1026 299 790 157 1201 123 1296 1168 559 1381 48 838 620 820 1225 697 1304 694 144 1388 135 1024 569 852 599 692 1015 457 1355 1425 1041 850 606 577 525 540 526 432 1297 1064 620 1089 649 633 597 648 544…
Output: NO

Constraints:

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

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