CT51274

Trader's Zigzag canals

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The quartermaster Trader has been asked to track the breeding season. On the desk lies a long table of canals readings. Task: Print YES if the undirected graph's nodes can be split into two groups with no edge inside a group, otherwise NO. Input format: First line: n and m. Next m lines: u v. Output format: Print YES or NO. Constraints: 1 <= n <= 2702; 0 <= m <= 5404; self-edges make the answer NO.

Example 1:

Input: 771 4487 1 2 2 3 1 3 1 49 20 770 716 762 254 603 8 734 121 718 156 625 169 334 207 230 10 514 11 747 22 518 407 534 52 126 144 280 338 427 145 675 527 582 335 474 22 406 383 548 328 599 78 183 431 696 37 64 113 636 355 402 197 390 520 656 110 152 299 577 75 545 21 602 198 341 203 720 123 310 123 691 246 727 633 691 487 771 226 727 288 704 69 685 689 742 163 503 630 662 61 285 467 506 617 683 513 533 215 632 126 646 351 512 233 323 99 223 128 461 158 278 323 329 656 740 383 469 81 214 498 538 57 478 387 546 41 471 134 492 464 603 79 656 479 725 317 471 71 422 269 747 197 271 345 556 3 29 95 683 338 358 72 644 704 714 289 344 170 308 270 436 368 488 120 569 37 88 58 353 85 134 417 553 301 647 125 202 177 516 487 746 302 533 359 721 372 467 135 405 575 721 139 643 198 460 671 768 255 762 80 6…
Output: NO

Example 2:

Input: 2475 2836 1990 2119 1430 1548 32 807 1600 1803 840 1894 612 670 1518 2413 817 2137 1524 2124 891 2335 325 407 87 226 291 1995 453 2023 1835 2418 600 1244 12 1753 73 1599 1164 1169 1439 2193 175 2178 364 2375 2276 2419 1631 1868 570 1243 448 570 1440 1592 740 1361 640 1095 596 1447 1372 2190 1512 2103 170 1712 224 1552 629 1018 93 1643 2082 2405 585 1754 1453 2084 623 1534 550 2355 996 2043 1010 2017 1017 2143 1360 1887 450 1736 1476 1923 1473 1863 290 444 256 988 802 1883 352 2311 1051 1398 1636 1737 2290 2363 1331 2307 1145 1425 259 290 832 1987 74 1505 28 2422 1371 2045 976 1282 760 2224 1418 2330 1277 1906 655 1043 1242 1865 360 2474 750 1181 500 1454 1230 1996 469 1348 248 1404 380 958 1669 1733 353 1487 1301 2124 1490 2151 975 1222 1799 1904 1947 2206 1325 1683 575 1150 2196 2258 1260…
Output: NO

Example 3:

Input: 1852 4639 614 1774 401 1684 562 1337 728 1596 563 1371 1444 1592 566 1328 339 1648 263 374 957 1587 625 929 1376 1746 634 792 590 1291 580 1502 403 605 29 1648 1004 1017 300 765 738 932 241 317 1049 1103 693 1224 900 1038 502 1569 238 520 67 607 325 1623 165 627 1069 1672 923 950 159 194 510 1303 1137 1574 315 1009 1377 1524 617 1615 221 604 102 951 1043 1103 806 1764 843 892 10 903 107 1119 248 1840 437 844 833 1776 85 924 223 875 1357 1378 380 1434 646 1053 1114 1531 376 1584 87 973 320 1687 1138 1637 398 835 413 648 269 1063 1252 1457 289 1226 349 1531 868 1267 992 1286 631 1445 135 1746 1006 1120 1510 1641 41 108 731 1423 1363 1489 1104 1821 367 1603 1014 1033 1362 1415 899 1361 415 1480 846 1659 84 397 1603 1673 678 783 938 1771 411 1015 805 1765 706 747 18 506 910 1322 1588 1601 1224…
Output: NO

Constraints:

1 <= n <= 2702; 0 <= m <= 5404; self-edges make the answer NO.

Loading...
Test Cases:No test cases
No test cases available.
Trader's Zigzag canals - MEDIUM Coding Problem | CodeTikki