CT60245

The tunnels Two Guilds Puzzle

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Curator runs the kiln at the obsidian flows of Blackglass. Today the books show a list of tunnels, and the numbers must be worked out before sundown. 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 <= 919; 0 <= m <= 1838; self-edges make the answer NO.

Example 1:

Input: 438 1206 1 2 2 3 1 3 42 197 84 391 58 249 28 371 179 336 21 94 24 141 173 340 63 97 229 436 44 122 40 73 73 403 19 341 32 181 139 152 54 413 16 248 284 362 71 207 9 217 6 77 8 193 122 129 78 148 202 281 218 438 14 45 232 282 233 293 19 91 98 341 145 157 281 315 93 240 70 398 84 88 2 301 296 342 190 211 159 426 64 267 182 273 232 425 48 347 64 95 12 289 125 381 130 213 156 358 172 256 53 192 54 67 288 343 89 197 128 132 182 324 127 184 158 160 44 390 166 272 14 388 149 188 28 436 283 316 240 424 155 189 78 142 332 375 87 379 108 285 108 276 130 285 125 330 154 407 104 260 48 70 317 371 152 321 120 313 271 345 142 414 176 204 42 409 216 228 48 425 96 281 84 398 93 305 156 234 137 255 65 195 192 275 94 169 169 426 172 320 278 293 290 351 294 437 30 186 163 188 45 88 51 389 47 68 234 418 170 2…
Output: NO

Example 2:

Input: 541 485 70 507 165 328 306 310 114 148 411 483 116 326 294 347 85 194 174 464 514 534 278 411 71 163 314 324 172 378 434 463 190 499 292 357 278 420 118 395 299 350 316 462 19 175 178 294 131 304 204 337 264 477 137 515 89 140 5 439 15 335 290 451 432 445 366 370 132 508 94 391 28 478 29 39 382 439 5 47 142 489 196 212 124 284 353 402 276 407 17 21 17 336 290 536 95 408 115 260 23 432 36 130 46 244 458 512 33 406 129 456 33 147 24 254 413 431 45 482 379 424 59 523 25 430 238 462 404 429 244 472 145 462 102 426 235 352 463 516 291 353 292 293 223 372 8 406 70 246 71 249 124 533 78 178 219 359 141 377 380 416 181 381 36 538 49 291 118 470 39 145 257 332 231 272 173 501 15 257 192 221 482 532 65 389 194 259 196 371 318 501 114 538 12 470 43 95 135 399 150 227 296 488 5 188 109 433 304 448 105…
Output: NO

Example 3:

Input: 412 1596 1 2 2 3 1 3 34 400 73 323 13 158 60 353 112 378 62 137 56 131 213 239 90 107 279 398 176 234 252 377 214 404 47 342 169 320 75 241 173 409 159 279 130 291 307 394 191 212 171 265 233 242 1 341 210 321 143 190 23 147 49 232 10 306 264 306 14 396 57 325 25 101 171 172 43 232 159 330 22 90 18 135 112 399 322 386 171 408 57 75 132 179 190 312 14 42 17 48 159 172 277 312 69 230 4 83 283 368 259 355 18 70 321 362 202 275 304 363 78 109 73 309 213 372 171 383 32 70 127 387 249 338 35 397 115 261 90 191 140 155 22 283 95 210 95 285 65 109 291 326 226 366 302 353 86 165 28 406 28 392 178 200 24 357 303 318 67 199 288 346 217 224 119 240 339 346 137 377 51 116 78 136 1 51 77 113 154 327 308 385 61 282 74 236 189 279 377 383 39 315 51 241 73 330 310 409 120 224 165 340 57 298 151 254 26 321 …
Output: NO

Constraints:

1 <= n <= 919; 0 <= m <= 1838; self-edges make the answer NO.

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