CT61097

The Two Guilds of Petalbrook

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Xavi found an old ledger of bridges in the exchange attic at the garden city of Petalbrook. 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 <= 798; 0 <= m <= 1596; self-edges make the answer NO.

Example 1:

Input: 354 1282 23 47 111 173 8 60 175 273 180 213 103 262 2 33 54 194 29 220 85 245 146 206 2 343 107 206 229 317 27 300 202 228 8 16 131 330 166 224 286 326 167 194 230 262 98 176 172 185 80 169 114 305 154 246 191 343 78 324 151 354 125 256 64 262 181 247 146 325 229 234 97 319 231 244 130 144 62 327 272 291 205 268 245 328 88 118 321 331 160 266 245 249 248 324 313 348 36 255 92 270 96 297 58 350 22 191 45 126 184 280 169 198 14 233 86 180 222 229 152 306 9 149 236 299 162 264 266 325 194 324 185 345 26 100 155 303 109 279 311 332 162 271 2 280 55 340 151 189 133 333 194 244 292 304 201 306 13 267 234 291 97 197 45 191 68 183 137 142 214 262 139 267 104 273 286 345 275 351 137 232 36 135 15 292 70 233 102 254 16 40 187 209 85 193 73 201 7 324 72 314 42 244 16 203 102 219 67 143 4 197 28 33 10…
Output: NO

Example 2:

Input: 456 546 1 2 2 3 1 3 242 435 164 300 69 235 183 218 14 424 237 256 70 121 204 280 132 309 2 207 154 247 253 357 51 408 130 289 2 217 143 220 319 451 157 197 93 170 244 311 327 425 149 241 375 437 73 333 273 309 129 201 103 105 259 308 264 388 200 342 146 164 45 298 190 216 171 210 86 133 105 119 211 270 394 454 10 327 195 242 94 168 57 404 1 311 300 330 93 393 10 431 81 454 301 445 9 414 336 394 171 321 103 265 333 399 239 343 107 232 115 370 258 407 220 337 49 439 105 343 151 163 40 61 105 340 114 158 43 185 177 445 239 402 228 260 128 133 22 345 373 454 163 407 88 197 68 417 15 260 231 353 360 405 326 404 10 63 154 212 222 350 44 443 4 359 14 107 80 312 23 432 304 404 54 189 22 143 253 351 53 245 64 315 81 303 32 316 170 382 15 199 114 229 291 384 288 447 167 262 74 211 173 285 3 217 167 …
Output: NO

Example 3:

Input: 705 838 198 442 203 533 122 375 386 625 204 563 104 268 64 687 105 622 83 163 79 334 24 285 244 399 54 664 4 321 254 360 470 661 398 423 112 259 51 89 284 525 21 652 107 162 137 611 332 562 206 236 87 166 253 435 349 359 519 575 155 614 102 249 224 569 326 519 253 671 129 604 441 674 58 513 216 502 52 87 386 685 95 581 19 153 264 630 243 545 110 424 240 560 137 335 114 292 280 625 317 562 247 295 343 664 113 410 130 432 72 422 123 270 232 510 66 159 626 650 320 666 405 573 118 401 528 627 6 636 312 355 267 506 59 282 575 599 197 403 270 301 90 181 214 284 215 679 233 527 41 346 332 650 45 685 449 690 487 653 316 451 229 276 340 466 507 652 545 660 138 140 358 387 8 272 277 438 109 597 193 197 46 297 47 507 398 484 55 358 92 157 116 302 360 502 476 516 170 553 356 373 296 480 14 525 18 228 …
Output: NO

Constraints:

1 <= n <= 798; 0 <= m <= 1596; self-edges make the answer NO.

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