CT59428

Sahil's Ledger of bridges

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Sahil the store warden watches over the gull cliffs of Screech Point's stores of bridges. A careful computation stands between order and chaos. 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 <= 1018; 0 <= m <= 2036; self-edges make the answer NO.

Example 1:

Input: 111 1769 1 2 2 3 1 3 52 96 15 43 12 107 94 99 40 70 18 108 93 105 4 44 60 96 56 93 1 33 16 77 66 78 52 103 71 107 36 85 23 49 33 54 25 46 33 42 40 81 16 49 61 86 73 111 107 109 92 95 10 65 9 72 4 55 99 110 8 100 41 97 52 92 25 29 26 43 9 40 4 84 14 40 81 84 87 110 28 61 7 61 18 80 65 100 52 107 61 97 43 77 45 52 70 71 51 66 15 88 51 100 26 111 33 88 33 36 6 39 45 63 11 70 8 64 30 90 21 90 67 109 56 59 33 72 54 60 17 22 29 44 57 69 49 82 83 104 79 82 15 22 23 59 69 80 4 28 1 5 53 98 1 80 41 59 27 50 33 49 37 72 39 95 26 28 60 87 6 89 1 55 15 82 21 100 56 65 10 109 40 63 44 95 27 53 79 84 53 60 11 15 4 57 66 75 16 38 36 69 8 10 33 80 35 94 17 83 46 59 44 70 96 110 25 28 2 38 9 68 19 59 9 42 51 63 48 77 23 66 32 99 34 73 17 59 30 99 94 97 7 106 24 83 26 53 44 60 18 19 9 17 35 78 40 66 67 86 3…
Output: NO

Example 2:

Input: 339 2024 90 179 65 69 184 284 198 282 152 206 13 217 57 93 164 224 59 275 61 69 224 294 18 335 190 309 226 276 130 259 175 222 42 224 51 84 105 151 15 339 175 267 41 50 17 326 8 246 250 308 167 323 127 218 204 338 281 315 128 231 107 194 19 120 126 274 231 273 10 301 47 315 18 41 181 229 70 80 109 221 212 321 180 199 42 162 123 183 137 280 15 38 67 285 240 247 80 223 53 112 235 334 237 330 42 268 23 29 115 257 210 310 88 96 84 232 21 318 85 310 8 222 162 284 33 244 10 327 106 108 230 231 177 265 3 145 116 153 154 160 9 249 88 219 64 277 159 230 74 115 186 293 8 16 34 100 138 271 99 239 77 264 16 60 168 333 317 339 10 164 26 216 9 122 92 225 43 121 68 85 53 125 1 132 2 309 6 127 321 331 235 238 83 332 130 175 238 263 61 135 95 225 90 281 12 335 155 247 22 253 39 156 137 266 213 325 69 175 1…
Output: NO

Example 3:

Input: 524 1459 332 411 283 386 469 504 82 268 349 416 116 389 131 473 240 331 177 439 58 522 40 44 150 216 190 370 61 371 133 509 375 378 57 496 185 265 478 510 277 392 223 352 236 286 11 357 58 99 8 196 89 188 178 300 318 340 234 422 439 441 128 225 163 310 44 125 115 453 53 93 128 365 118 385 386 422 294 315 89 403 140 418 19 428 245 425 253 414 264 319 371 433 164 440 22 287 347 356 211 278 325 379 22 159 161 357 153 270 202 485 67 185 8 358 119 218 206 443 294 365 471 517 467 477 21 221 304 373 419 520 111 165 69 373 339 375 390 487 15 66 135 251 202 366 177 419 82 84 301 443 184 309 115 284 189 429 48 229 179 440 388 515 212 222 20 82 400 495 191 372 96 191 205 230 105 330 131 485 297 425 380 468 159 521 104 426 57 486 440 474 178 215 379 439 378 503 321 519 245 300 170 182 213 254 74 146 8…
Output: NO

Constraints:

1 <= n <= 1018; 0 <= m <= 2036; self-edges make the answer NO.

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