CT40990

Archivist Counts the bridges

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Archivist the bookkeeper watches over the garden city of Petalbrook's stores of bridges. 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 <= 2017; 0 <= m <= 2017.

Example 1:

Input: 513 1667 103 11 295 155 276 182 191 338 58 397 125 11 382 486 35 60 252 216 482 157 43 374 237 379 182 169 246 15 471 301 511 389 426 448 420 88 416 490 269 243 66 498 432 107 418 391 354 218 148 428 246 491 329 228 474 239 97 423 223 399 213 295 301 138 431 390 444 212 502 29 247 387 489 226 133 42 280 231 479 200 85 502 220 464 479 472 174 177 433 488 214 257 69 256 459 266 286 306 24 142 301 375 88 260 469 163 378 443 105 284 152 18 135 147 146 33 466 452 266 217 291 293 105 412 42 129 106 124 457 336 460 9 371 460 152 276 317 456 70 476 50 345 148 324 363 438 30 115 375 498 97 24 159 392 185 283 257 126 400 316 252 494 311 306 476 21 172 34 13 312 242 256 252 131 130 461 379 155 460 7 509 141 283 416 295 432 333 447 100 76 72 188 419 99 326 148 490 107 133 59 513 103 392 333 328 492 47…
Output: YES

Example 2:

Input: 2006 1955 378 847 1464 1213 1073 1498 1885 472 1466 1420 1890 135 745 758 1775 1071 1291 155 1906 1665 1824 386 65 1619 327 511 1200 929 1864 810 867 1885 904 1144 163 219 1982 522 645 1012 1243 1100 824 1383 245 900 491 669 1751 1395 401 1445 1636 1685 753 1178 139 1356 38 193 301 1332 426 1441 963 339 1968 11 1151 1163 1223 299 1506 1319 17 1856 772 228 300 1950 1986 599 302 1844 1512 1831 322 1247 1188 1163 1323 1007 1890 357 1140 72 1360 1976 445 1375 391 1697 352 1307 285 903 1881 1032 1148 1949 745 764 629 1821 330 457 916 1540 939 588 1737 1731 1079 1799 1955 338 1567 1216 1417 1263 924 1899 1433 1377 203 1187 878 1058 609 1639 904 340 1939 551 1444 563 740 341 413 1237 559 1693 1902 1180 953 1589 579 1185 1775 249 1216 894 1324 81 410 1081 586 1269 482 568 58 1326 87 1650 1661 1280…
Output: YES

Example 3:

Input: 1599 667 484 107 740 169 404 774 813 654 660 1102 1542 1591 1484 1448 702 313 248 1043 488 1464 973 492 808 901 344 916 28 57 61 1046 336 84 584 984 203 1143 1174 260 452 41 205 821 828 1399 4 1318 1347 235 39 255 1050 120 1027 871 891 645 897 426 1545 1392 776 907 1193 1121 143 148 815 1316 1298 717 53 641 451 11 332 139 1331 715 944 1172 1166 538 1557 1494 1211 1279 728 1106 524 1517 419 342 1268 1486 1418 1542 539 1459 1289 172 93 331 1547 818 630 1489 868 888 1118 1565 1000 1577 1045 1100 84 424 1381 419 1062 626 130 85 1593 790 955 1325 616 508 790 1234 339 1433 446 1276 397 13 373 1019 1323 1344 990 250 1202 56 1310 264 520 1377 217 63 105 569 365 275 1433 993 534 1434 944 909 911 977 11 998 997 334 212 193 1216 930 1373 1380 141 864 1497 1473 720 1177 1531 414 84 1139 59 835 1463 59…
Output: NO

Constraints:

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

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