CT57252

The bridges Two Guilds Puzzle

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Dorian inherited the gallery at the river town of Willowford along with its curious bookkeeping system for bridges. Time to make sense of it. 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 <= 2843; 0 <= m <= 5686; self-edges make the answer NO.

Example 1:

Input: 1026 925 820 879 22 257 356 452 5 350 481 644 563 765 345 568 392 978 6 810 100 231 28 329 274 860 141 596 116 754 244 505 576 662 449 893 766 833 714 902 34 216 390 497 124 266 877 1005 80 579 699 841 636 643 436 716 193 362 130 436 518 961 426 638 267 872 235 630 118 726 209 781 371 646 376 810 111 439 145 717 14 69 47 72 301 517 495 975 11 532 312 450 306 739 10 442 470 712 511 1022 298 363 265 808 254 545 321 826 503 747 121 393 115 341 201 293 470 927 271 381 287 885 574 897 191 258 527 1010 119 362 445 931 130 646 345 820 482 871 329 594 237 248 163 813 32 781 393 479 524 682 711 1025 45 640 759 886 23 966 430 588 461 531 311 684 446 486 151 266 206 476 120 823 738 984 124 610 313 754 423 672 85 1005 199 316 15 952 22 775 286 634 233 517 88 353 824 851 407 565 209 556 211 815 427 543…
Output: NO

Example 2:

Input: 1697 5015 1049 1161 188 1291 352 1223 783 1209 219 1223 59 1494 769 1435 419 873 165 1611 774 1589 68 1505 425 1202 157 1464 356 720 450 481 578 1190 440 841 1010 1670 214 354 971 1352 287 1269 724 1607 395 1037 221 1418 1625 1656 1052 1442 421 1087 258 1032 1493 1543 836 899 1615 1681 579 630 18 1169 1128 1161 204 986 871 1466 248 1208 47 379 826 1026 89 740 896 1681 423 1383 244 323 2 1626 535 1668 180 1661 1448 1595 727 1241 845 1673 1288 1301 497 943 628 1196 587 872 975 1404 340 862 1156 1566 1066 1263 204 1638 117 544 571 1227 235 1482 556 1229 555 912 431 1652 111 652 346 1562 373 917 1245 1274 823 1310 469 694 352 937 893 1595 1313 1423 484 594 286 523 333 602 1035 1098 25 1350 225 1233 518 1422 959 1552 1495 1514 96 1344 404 1553 152 1271 772 1189 402 1393 1009 1515 690 1510 32 12…
Output: NO

Example 3:

Input: 2732 3150 1 2 2 3 1 3 821 2716 975 1758 2101 2148 1128 1172 163 2717 119 1024 1162 2364 795 1200 75 204 523 2599 1098 1202 1263 2009 450 2203 1499 2539 1253 2257 897 2311 19 1863 1391 2584 71 1876 1399 1885 416 2592 1057 2411 90 176 121 1913 1700 2067 1146 2615 2200 2318 585 2104 327 2009 616 2298 2518 2535 1481 1626 267 1466 870 2149 1663 1968 774 2464 230 1697 947 2181 2354 2483 605 2633 457 2253 1079 2347 1342 2138 280 1506 128 130 45 2461 517 2520 1592 2086 2302 2722 696 1268 700 1503 2189 2372 276 2468 74 969 2297 2469 1718 2166 398 1448 453 2576 275 2525 728 2396 1159 1458 1339 1613 213 531 939 2295 1687 1868 406 2107 440 2082 1990 2298 758 2215 1744 2370 1977 2664 506 2421 1317 1731 77 1304 684 1955 149 907 655 718 288 1637 950 1037 178 325 926 1867 84 322 703 1317 678 1865 793 806 …
Output: NO

Constraints:

1 <= n <= 2843; 0 <= m <= 5686; self-edges make the answer NO.

Loading...
Test Cases:No test cases
No test cases available.
The bridges Two Guilds Puzzle - MEDIUM Coding Problem | CodeTikki