CT43427

The Two Guilds at Briarthorn

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the forest village of Briarthorn as Dev unrolls the day's manifest of bridges. The tally will decide the next shipment. 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 <= 2154; 0 <= m <= 4308; self-edges make the answer NO.

Example 1:

Input: 396 2389 124 160 234 335 54 333 55 239 94 367 146 353 108 259 226 308 28 147 42 141 31 208 60 320 83 317 218 245 132 205 122 351 208 245 334 380 251 264 218 250 131 235 321 358 90 182 198 319 47 192 100 277 55 127 102 373 42 147 32 188 227 269 97 360 130 330 99 136 102 259 147 369 159 292 1 202 254 297 260 270 73 162 195 322 86 285 221 360 110 335 52 200 24 160 314 369 26 329 179 258 53 85 29 379 251 373 90 331 2 270 130 274 61 159 356 359 163 242 43 349 84 180 38 305 254 267 137 226 94 196 66 362 137 180 225 244 328 374 84 227 155 295 268 343 2 170 229 292 107 394 142 160 10 384 290 326 240 323 68 239 33 282 66 83 349 376 143 213 8 68 31 376 32 135 236 296 79 230 64 217 294 386 67 363 262 296 188 367 221 226 261 328 98 374 4 135 140 345 199 234 27 184 106 345 75 309 84 378 200 220 56 191 …
Output: NO

Example 2:

Input: 1551 2170 1 2 2 3 1 3 403 1371 672 887 43 1149 631 1413 277 1338 466 479 1003 1137 905 1474 445 636 852 1549 488 861 379 1412 267 1043 581 1267 143 962 438 705 848 1132 381 1325 552 660 147 998 466 541 1064 1421 809 854 60 991 1409 1515 885 1135 240 246 293 1417 239 1060 989 1117 495 837 1094 1340 316 895 973 1322 327 1452 503 1078 427 1043 429 478 180 501 925 1090 531 1206 1093 1244 554 1459 361 582 634 1404 958 1082 637 949 668 956 161 452 869 902 557 1469 946 1118 412 566 602 1322 123 920 491 695 370 792 630 1428 1009 1541 658 890 594 628 234 1161 311 1345 884 1441 409 502 573 1016 251 828 268 1530 214 357 717 1011 175 891 72 153 619 708 152 483 385 684 344 1091 517 1196 646 998 188 1096 703 893 614 709 250 646 697 1227 1205 1450 44 418 1378 1444 574 770 1027 1516 1269 1282 495 1306 629…
Output: NO

Example 3:

Input: 1521 499 201 640 874 1093 685 1276 406 1340 750 1112 228 617 324 403 22 187 370 581 1392 1431 655 1124 489 747 555 896 393 1212 526 656 390 855 88 366 67 588 182 545 788 1448 1006 1177 598 1078 143 159 360 675 186 248 814 900 299 686 567 753 248 345 687 1451 370 1229 194 1423 268 311 1105 1208 1016 1066 1323 1501 255 533 659 666 1234 1399 256 502 1017 1156 431 794 331 1101 344 1496 855 1342 403 1486 400 472 95 348 673 1241 559 1169 65 378 443 793 568 1326 26 194 523 984 804 1006 41 236 141 1044 764 1441 711 831 748 1183 5 366 923 1409 75 229 419 785 1292 1515 719 1233 787 1231 774 799 259 1437 36 72 883 1265 238 1056 226 732 210 1030 660 924 1208 1339 842 1231 1484 1488 719 1323 242 411 1029 1428 530 1037 382 1407 780 966 285 1346 22 1037 622 1408 311 782 405 1380 374 1442 678 1400 18 239 …
Output: YES

Constraints:

1 <= n <= 2154; 0 <= m <= 4308; self-edges make the answer NO.

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