CT63655

Harish's tunnels Two Guilds

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Harish found an old ledger of tunnels in the chandlery attic at the basalt cliffs of Obsidian Shore. The margin notes pose a precise question. 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 <= 1947; 0 <= m <= 3894; self-edges make the answer NO.

Example 1:

Input: 1074 2651 151 505 155 829 358 786 199 438 258 433 161 997 465 506 581 954 565 843 108 227 844 1035 32 645 233 518 784 860 7 813 106 702 58 702 250 1069 784 1043 95 1041 761 1070 669 795 173 639 98 797 224 332 555 640 394 769 682 686 225 517 515 782 703 727 533 611 87 749 191 554 321 366 409 752 69 78 324 987 155 396 160 515 356 1057 118 487 123 1014 267 1043 274 808 27 927 946 1009 393 865 800 854 339 901 808 1057 802 1025 421 822 293 888 79 207 239 701 122 389 375 418 735 863 913 954 480 981 236 275 742 854 410 544 621 701 393 1044 269 297 221 902 25 1025 137 659 149 553 768 792 139 405 35 418 499 928 351 554 808 1070 619 943 103 584 22 105 648 921 392 598 207 596 241 805 821 859 496 783 797 926 10 638 425 494 693 759 156 917 421 601 342 997 340 1073 510 673 329 747 522 764 271 808 401 41…
Output: NO

Example 2:

Input: 443 148 225 250 218 375 114 192 19 122 129 425 252 424 234 393 32 66 121 421 296 392 27 68 175 298 241 248 129 199 165 388 230 328 10 182 73 330 262 416 62 195 159 362 162 243 212 310 178 405 58 65 174 356 368 422 7 76 47 181 306 350 27 235 12 412 253 255 168 305 46 388 103 230 142 355 116 122 31 301 335 355 114 116 113 138 51 272 74 113 89 239 328 411 354 433 195 387 93 223 285 435 156 267 267 407 12 113 165 307 28 272 45 134 46 179 25 430 14 358 54 277 344 436 10 179 345 401 112 349 127 386 79 84 287 373 177 441 109 322 231 405 125 194 56 318 295 412 13 353 124 352 263 396 66 140 62 288 282 431 64 100 96 322 163 329 150 246 218 284 233 368 114 315 215 232 48 151 66 408 70 77 354 379 17 139 156 224 24 257 3 235 253 386 76 115 69 415 318 430 189 387 64 137 122 280 67 316 80 390 121 430 204…
Output: YES

Example 3:

Input: 1565 3153 1 2 2 3 1 3 146 242 505 1492 314 1405 294 1261 424 1559 549 898 1166 1235 612 1343 293 973 618 1082 729 945 1066 1188 106 1400 381 1429 601 936 197 1483 1061 1455 851 1281 683 783 865 964 98 1341 640 1450 532 1066 267 362 55 885 1053 1213 345 909 435 574 354 688 518 667 56 656 861 1528 547 657 150 1487 808 1259 137 1518 1234 1487 39 604 764 1311 411 1303 111 1548 67 1345 871 1259 98 1248 277 513 229 1553 252 1503 574 869 316 494 729 744 725 1111 17 834 356 528 646 716 856 1009 1198 1208 945 1043 104 1500 795 1432 181 1206 1 1190 18 1376 217 226 628 960 1087 1154 220 1105 30 780 570 1097 844 1456 1295 1334 232 1327 261 1015 1245 1269 228 1319 838 1444 273 1310 318 495 369 1295 903 1493 131 671 888 1460 16 1498 1229 1550 242 649 402 629 123 662 884 1390 259 1288 106 333 1211 1380 8…
Output: NO

Constraints:

1 <= n <= 1947; 0 <= m <= 3894; self-edges make the answer NO.

Loading...
Test Cases:No test cases
No test cases available.
Harish's tunnels Two Guilds - MEDIUM Coding Problem | CodeTikki