CT57729

Nils's tunnels Reckoning

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The registry keeper Nils has been asked to plan the harvest festival. On the desk lies a long table of tunnels 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 <= 1716; 0 <= m <= 3432; self-edges make the answer NO.

Example 1:

Input: 1713 2837 1247 1375 1002 1565 192 1199 688 1418 98 1094 413 745 582 1324 800 1545 979 1011 227 230 322 421 1290 1708 191 279 832 1351 38 1436 195 1236 115 800 640 844 455 482 656 818 212 263 263 1494 704 725 741 1580 114 713 343 1376 291 398 971 1585 387 1635 1611 1691 267 505 336 443 67 372 441 570 74 1326 1242 1458 217 1174 256 1674 839 1512 1583 1711 301 1003 184 1157 171 1431 761 1136 829 1708 156 1223 100 1652 1286 1438 806 869 107 126 744 1216 686 1514 46 1483 112 742 34 598 447 1672 151 673 67 158 511 1585 102 419 218 355 1124 1477 142 1155 715 791 585 1106 577 1072 522 1315 1089 1310 734 1550 735 1661 932 1175 103 799 286 1447 191 993 1019 1298 837 1484 997 1228 1276 1353 387 680 419 579 287 1010 628 968 549 554 951 1295 1161 1495 958 1304 175 341 474 1651 896 915 274 1003 424 1050…
Output: NO

Example 2:

Input: 857 2653 222 257 225 550 115 710 4 366 668 701 17 28 7 397 508 641 284 789 22 255 240 342 307 681 587 706 673 692 379 425 282 490 647 698 193 755 102 443 1 535 554 592 163 841 222 255 27 293 109 121 438 506 507 840 568 801 46 305 144 598 151 373 262 688 601 643 37 65 25 629 798 815 122 153 45 558 523 723 280 297 109 635 211 237 308 683 20 533 377 534 536 678 230 391 527 844 37 291 406 760 108 841 95 219 43 684 716 752 449 702 26 400 540 786 387 465 398 641 524 813 469 510 510 742 654 821 324 445 694 786 513 814 444 762 350 800 123 479 695 724 22 543 561 580 287 805 329 850 335 394 268 503 372 717 137 798 119 468 375 719 155 551 354 475 292 553 168 340 276 636 408 610 250 337 124 330 396 529 329 501 701 795 232 853 232 315 400 595 709 824 108 675 451 501 295 641 18 450 546 826 703 724 616 6…
Output: NO

Example 3:

Input: 329 1545 63 157 30 257 116 202 158 297 129 283 100 235 41 262 82 259 164 194 54 308 219 285 213 255 7 66 88 128 148 223 40 201 175 233 34 277 69 281 71 217 87 270 13 185 52 108 146 215 136 151 104 195 8 232 118 212 43 84 79 318 104 288 49 119 131 187 166 277 39 79 6 57 4 245 174 279 255 312 277 324 190 221 162 321 33 244 55 256 10 134 40 268 254 315 108 173 140 176 48 167 116 321 159 165 196 253 146 299 52 230 28 226 143 323 7 222 5 109 148 308 10 306 94 165 217 305 254 320 41 215 44 283 191 329 33 189 27 197 307 324 264 292 134 324 142 209 69 133 106 324 38 160 199 216 189 190 134 194 65 140 160 318 128 273 84 290 21 149 91 109 185 218 84 110 51 160 65 82 149 269 186 315 210 214 12 291 145 252 305 328 173 252 156 200 183 261 137 237 42 265 100 264 181 281 158 301 193 219 92 169 51 311 226…
Output: NO

Constraints:

1 <= n <= 1716; 0 <= m <= 3432; self-edges make the answer NO.

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