CT30273

The Fewest Hops of Brasshaven

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Chandler found an old ledger of tunnels in the archive attic at the old quarter of Brasshaven. The margin notes pose a precise question. Task: Print the minimum number of edges on a path from s to t, or -1. Input format: First line: n m s t. Next m lines: u v. Output format: Print the BFS distance or -1. Constraints: 1 <= n <= 1176; 0 <= m <= 2352.

Example 1:

Input: 259 1178 1 259 187 254 42 166 29 127 182 191 214 256 102 112 37 213 119 199 128 138 104 190 126 146 78 182 72 194 81 176 119 148 8 185 130 227 135 204 167 186 1 222 164 178 10 153 89 203 143 154 88 100 61 219 26 118 95 153 79 154 64 234 17 114 83 258 78 233 215 245 100 214 40 42 207 245 23 258 21 246 250 252 47 84 112 233 204 257 9 101 168 203 135 232 59 75 29 207 129 209 40 161 42 151 41 129 101 128 94 219 27 136 55 134 13 61 64 81 179 215 62 75 128 136 20 58 57 251 126 141 49 90 158 174 191 196 91 207 166 175 60 80 19 39 10 59 25 66 19 205 111 197 54 83 166 209 93 162 86 145 56 95 121 237 142 198 221 258 188 238 74 114 127 171 42 110 89 250 135 186 59 253 99 121 104 118 51 253 113 168 81 121 74 95 56 187 48 251 111 250 150 255 171 249 172 259 12 183 80 211 53 216 243 252 55 234 36 127 16 27 153 158 22 37 23 226 120 137 48 162 86 192 147 170 58 209 84 181 99 203 80 255 67 222 92 252 62 138 51 192 155 257 75 92 5 184 32 113 132 176 34 93 105 225 43 120 115 178 136 178 38 154 35 146 33 77 150 187 86 259 208 257 139 212 83 241 152 153 33 233 104 127 46 206 209 213 82 205 37 187 225 234 66 142 227 240 67 206 114 152 44 117 111 170 24 145 21 99 103 144 100 159 134 256 52 59 148 257 89 252 169 240 16 229 43 82 14 116 115 124 31 209 38 163 50 129 62 95 162 239 51 191 26 29 63 235 75 241 37 171 86 232 100 184 68 256 129 258 65 253 142 165 86 158 136 164 34 132 6 84 21 105 176 255 118 244 95 244 111 135 47 102 93 116 75 256 46 231 155 177 221 247 77 136 28 170 141 163 108 181 100 109 202 231 207 251 70 195 186 220 146 173 77 214 31 136 32 101 49 222 7 228 235 258 61 216 12 64 25 141 54 101 27 244 230 258 71 249 164 225 66 93 105 127 18 162 93 237 94 184 38 46 148 245 8 82 135 153 68 139 52 168 124 188 72 128 43 240 88 146 15 50 132 162 99 151 134 211 128 237 95 99 31 213 8 251 122 194 73 231 35 161 57 157 81 221 70 176 61 70 154 224 121 191 176 196 115 231 120 222 62 86 47 104 159 188 128 169 144 227 29 35 151 209 174 243 130 174 98 141 135 189 122 130 16 46 98 183 12 114 54 144 61 165 66 79 80 180 74 160 60 247 22 140 105 208 51 72 39 149 7 128 75 250 94 190 12 57 4 244 196 229 28 244 121 158 9 118 15 88 55 257 157 159 57 168 65 190 3 101 68 159 131 259 64 185 115 226 166 227 239 251 133 253 146 231 69 222 138 241 157 184 112 217 22 200 114 168 40 137 101 150 238 243 25 43 27 114 3 233 54 236 12 212 33 66 83 198 85 235 57 138 109 162 83 227 141 209 168 195 8 216 84 142 9 192 46 230 1 211 5 134 151 242 82 178 164 206 152 216 4 107 161 167 80 127 33 169 15 61 241 254 167 230 127 213 124 221 111 191 75 80 89 201 64 73 28 31 69 197 185 230 51 214 72 101 38 246 104 193 148 248 158 210 45 241 33 37 142 169 56 124 204 206 114 196 128 197 60 142 91 200 180 240 199 217 44 218 19 87 64 198 23 168 117 152 18 58 7 212 168 218 155 208 34 141 39 219 67 201 30 156 19 234 79 123 26 31 211 227 24 82 80 117 12 21 19 122 124 155 139 203 19 110 136 184 52 216 68 78 21 257 124 237 5 62 169 257 73 97 32 35 61 208 70 192 39 221 21 68 21 109 48 117 54 172 4 246 99 258 4 117 5 172 138 237 65 137 30 37 41 258 79 111 185 190 107 108 44 173 144 256 13 113 89 146 130 168 93 145 145 188 62 116 75 230 3 36 56 105 162 186 164 224 186 238 52 215 113 238 180 243 190 199 164 250 116 190 64 134 87 233 130 139 124 167 34 223 16 220 158 246 32 40 23 165 50 224 125 204 1 176 1 215 194 242 116 179 224 227 74 158 70 76 112 185 122 193 105 132 91 149 176 191 114 180 163 195 93 222 152 166 95 170 159 223 93 191 124 202 176 221 193 255 68 98 28 46 82 202 51 82 63 72 66 75 194 231 100 259 115 190 119 212 64 237 27 181 46 163 169 232 44 208 138 142 59 212 35 208 74 168 67 119 51 209 52 233 13 120 46 95 149 246 170 229 19 226 143 245 89 194 46 61 47 244 151 175 56 166 112 118 46 140 141 145 101 168 77 253 34 258 153 206 23 32 79 179 189 217 11 215 21 231 2 30 54 168 39 198 138 250 26 79 172 180 182 197 37 74 29 239 103 126 27 134 2 56 52 164 77 141 84 232 18 122 37 202 61 186 37 54 75 167 103 221 85 103 64 158 63 211 177 213 80 98 78 133 73 93 21 94 36 232 9 144 163 258 140 258 4 158 63 124 114 154 217 249 107 235 87 248 106 200 162 221 33 181 172 254 79 177 63 188 178 231 116 160 20 37 11 182 17 35 46 106 155 200 232 235 16 116 97 235 28 190 2 119 59 90 32 186 89 183 164 185 98 191 112 172 45 105 23 125 8 122 63 87 55 112 92 256 109 244 142 189 85 252 53 122 20 157 38 239 150 178 195 203 77 257 114 176 204 219 53 179 143 230 194 227 48 157 18 205 68 239 74 190 64 149 8 113 157 217 43 236 4 18 110 139 35 119 21 151 28 223 96 201 107 207 108 258 46 179 142 193 191 248 49 245 134 184 56 204 124 143 94 251 53 151 205 222 126 220 43 230 85 200 71 254 237 250 38 211 111 241 79 203 155 210 89 253 140 194 56 94 43 168 155 209 10 162 209 227 85 242 44 165 217 224 20 123 30 183 64 243 239 249 127 149 70 229 83 159 115 251 36 256 207 210 44 234 35 184 84 259 77 199 124 141 147 196 66 218 106 130 4 237 135 145 12 141 34 213 127 196 175 227 58 83 2 178 135 248 158 197 13 39 26 34 24 248 163 216 3 42 14 107 122 166 28 219 167 221 106 196 21 156 2 205 21 92 4 25 66 129 169 242 67 215 77 182 147 228 77 196 215 256 106 147 86 170 102 154 20 212 188 234 32 241 239 259 26 180 97 158 85 145 69 239 21 82 25 123 2 157 152 192 102 216 164 215 38 138 115 126 41 68 132 220 109 169 21 254 87 245 42 127 159 166 75 113 34 60 32 139 110 120 111 200 20 69 131 168 170 211 67 162 72 164 135 202 187 197 172 202 139 160 150 175 55 100 6 129 41 105 55 86 123 244 51 109 98 182 128 257 125 212 26 73 243 253 33 75 143 222 48 191 28 129 73 255 96 181 125 215 102 124 197 240 31 169 38 98 26 108 2 91 20 139 20 192 39 147 28 209 149 178 93 253 35 223 76 159 64 178 135 201 129 141 65 96 96 115 154 253 198 215 36 154 101 106 121 139 15 24 3 34 116 157 75 237 83 181 17 62 37 229 72 111 60 179 85 256 99 234 108 203 37 71 120 176 154 175 46 221 12 155 172 235 191 220 35 201 91 238 106 219 27 116 115 150 76 167 208 223 13 52 26 230 7 237 63 103 39 152 13 246 31 173 107 178 56 186 193 199 114 128 33 64 203 224 66 243 42 57 36 64 58 228 199 200 34 246 108 119 66 81 203 251 29 163 47 103 79 231 98 216 15 99 21 141 75 146 45 249 162 166 36 259 18 116 22 104 17 42 177 194 108 256 73 195 39 62 105 113 5 88 90 155 115 196 169 223 2 173 55 193 12 236 5 210 222 257 31 100 101 205 106 198 115 183 119 142 45 89 186 218 93 108 107 243 63 192 16 231 19 185 60 126 107 134 1 177 7 224 180 203 184 222 41 147 11 236 15 48 17 252 70 235 177 198 66 143 111 235 131 159 54 75 107 213 129 218 203 236 154 238 15 126 178 214 58 67 66 231 33 103 108 202 3 132 70 150 130 149 19 115 50 236 18 156 70 74 16 85 108 167 162 170 133 235 55 150 54 253 150 257 1 80 103 244 60 212 56 190 94 221 180 188 204 230 107 136 73 234 119 229 42 108 33 97 71 74 104 170 65 156 81 140 188 248 28 218 98 136 9 30 28 174 2 217 49 135 169 219 108 188 97 185 145 151 13 202 100 119 168 201 153 227 42 134 1 40 177 186 179 203 32 64 49 240 222 244 147 244 54 113 100 182 53 219 61 104 20 156 174 185 227 231 53 250 44 148 28 107 130 205 148 210 154 228 106 258 29 168 53 169 197 212 102 113 177 179 103 148 43 110 45 230 220 244 14 134 23 143 141 147 98 219 153 213 46 111 70 209 111 179 86 253 67 88 34 57 198 223 122 180 81 220 129 223 30 198 84 187 192 228 54 224 23 244 232 250 95 208 253 257 152 257 24 44 13 124 87 93 83 117 4 220 84 206 87 134 140 155 145 163 3 134 30 42 162 218 156 179 61 169 225 253 84 222 34 170 74 82 133 168 160 234 236 244 78 150 29 173 14 70 122 172 60 223 3 62 83 158 67 219 36 160 25 250 105 244 21 163 78 216 35 47 130 172 126 150 201 218 73 168 31 183 97 244 50 133 176 188 74 184 74 113 168 242 82 165 13 183 17 165 136 245 79 178 152 221 71 91 86 181 225 239 21 149 58 126 156 173 49 103 107 155 36 185 103 184 145 190 75 206 180 184 7 55 44 47 38 70 185 203 76 184 17 150 49 55 167 223 127 250 112 180 68 118 92 215 208 215 199 245 92 242 172 239 30 47 90 203 89 112 24 25 49 83 127 231 202 221 64 193 99 200 244 249 12 99 49 247 131 255 38 160 59 214 32 158 22 33 174 254 47 109 81 168 121 144 91 243 51 124 139 165 69 184 39 105 18 65 73 253 89 215 81 195 99 102 76 112 204 231 19 182 94 111 184 197 27 249 85 89 76 252 105 154 45 65 179 232 111 161 129 161 124 173 91 152 57 191 195 254 148 253 163 173 113 144 164 183 7 70 199 226 34 195 4 133 96 139 142 218 86 109 118 250 32 68 19 73 33 220 67 212 144 233 49 131 159 218 34 125 66 255 38 232 33 53 181 222 23 147 12 188 84 217 171 256 139 186 106 217 117 188 30 141 60 177 136 249 223 240 90 252 14 21 76 208 123 228 246 249 30 151 193 250 22 76 159 174 184 199 70 168 89 160 46 124 81 126 23 192 94 175 32 196 56 259 45 154 6 139
Output: 3

Example 2:

Input: 623 1892 1 623 16 478 377 427 327 563 334 340 22 44 128 365 104 126 431 456 130 164 11 506 392 510 237 340 108 615 236 477 421 460 203 501 161 235 34 225 111 515 162 538 274 320 14 107 94 481 404 535 350 507 163 196 55 180 232 574 15 455 44 480 322 374 226 568 28 206 392 483 235 617 117 149 493 545 177 206 68 401 223 484 197 526 102 215 6 363 411 430 220 242 322 516 374 486 179 364 162 593 58 273 84 420 234 510 327 493 51 602 336 573 265 358 387 568 23 209 478 533 521 557 43 244 189 301 522 540 12 569 234 316 261 394 293 305 272 358 498 554 318 538 136 164 293 438 138 146 76 375 82 153 12 239 188 472 110 474 24 621 363 403 602 605 385 623 32 476 158 358 85 93 412 426 152 588 271 421 299 505 14 277 65 597 385 545 300 331 82 130 199 367 528 566 85 135 195 549 113 259 450 607 186 468 250 355 185 436 65 594 351 420 173 544 420 607 269 589 36 68 114 217 124 350 535 605 154 156 59 137 23 29 83 431 3 457 230 560 387 502 227 595 269 497 54 180 35 334 42 348 35 556 296 343 241 328 112 142 203 460 8 211 272 500 113 166 55 229 615 623 311 357 322 594 320 473 44 308 484 513 151 183 120 488 254 367 186 343 379 420 151 492 267 417 550 593 380 428 22 559 35 543 118 542 285 315 56 230 373 527 388 536 406 554 147 505 295 313 233 565 269 329 331 595 28 495 27 174 62 214 132 501 174 297 30 425 112 565 43 579 128 194 207 465 69 72 300 470 18 411 184 612 91 237 101 549 210 522 235 384 223 514 323 532 42 342 122 267 279 443 119 261 201 487 139 351 214 501 175 360 523 594 253 278 300 332 26 248 104 373 110 344 322 355 15 617 388 609 352 566 91 581 8 585 239 515 237 491 513 518 320 407 341 620 206 340 147 567 258 454 193 348 168 409 387 426 283 580 62 163 263 285 6 357 382 523 42 233 188 280 97 206 112 131 255 607 120 191 23 424 275 426 357 513 353 465 205 549 173 421 82 99 366 538 96 252 444 468 130 603 232 509 307 545 84 226 376 502 300 576 135 404 63 437 453 561 78 93 317 371 150 586 492 513 97 599 190 233 141 264 104 218 86 213 146 189 320 527 180 481 119 339 39 586 52 94 9 418 44 464 71 309 506 519 43 615 45 275 372 529 436 469 146 332 99 399 317 622 214 528 558 592 403 412 305 390 71 572 26 61 414 529 54 296 92 485 492 577 188 404 215 255 12 276 112 522 106 440 72 321 245 463 254 528 158 170 108 591 74 92 228 359 230 511 78 226 243 323 84 491 45 547 2 112 103 287 140 493 12 124 434 456 155 551 18 501 308 360 496 497 49 577 10 45 286 590 108 371 295 357 348 546 387 463 28 122 48 404 177 571 406 555 141 208 6 69 180 376 201 278 72 228 107 434 101 236 601 607 384 517 6 577 141 455 216 248 513 539 258 544 165 244 49 65 447 536 15 379 184 355 132 551 151 253 354 380 43 317 329 575 246 291 102 344 101 571 255 351 12 191 34 404 58 585 475 540 254 501 365 404 321 352 110 512 14 561 492 603 318 408 80 377 123 572 284 436 173 410 236 485 33 346 342 506 154 582 133 315 3 335 162 541 5 236 272 396 166 448 205 389 120 175 118 261 390 544 249 486 71 333 211 355 249 596 203 514 412 604 257 586 22 444 101 307 219 562 252 594 79 558 249 309 357 421 451 537 492 606 235 607 250 620 284 600 25 308 289 342 20 26 528 544 353 456 197 246 268 410 418 468 108 379 422 444 7 47 115 410 84 353 41 541 31 593 118 276 103 525 33 440 94 370 309 324 401 414 431 499 31 132 177 498 41 597 305 493 117 260 214 560 445 477 463 471 11 526 497 597 93 563 119 125 527 555 478 596 292 581 1 478 6 401 191 221 234 465 262 418 19 504 214 437 24 585 230 277 295 622 133 248 263 525 147 167 295 573 358 444 8 186 212 319 205 298 551 594 220 226 178 549 551 587 320 361 299 422 275 613 35 83 68 402 181 539 190 249 4 16 302 346 382 530 431 469 132 176 41 475 93 490 111 214 105 464 102 306 284 462 2 442 550 557 81 447 3 424 52 251 178 371 240 472 267 502 233 494 523 561 35 115 236 579 99 250 132 390 44 312 203 246 353 470 7 83 352 464 314 432 349 581 41 161 172 248 91 461 321 428 117 231 306 427 1 70 458 604 42 116 393 614 170 612 203 464 94 488 179 317 107 282 480 585 148 537 2 164 446 484 261 405 181 619 401 582 475 503 99 494 361 466 459 593 551 567 354 615 272 426 388 612 266 580 121 223 221 441 164 544 4 570 54 228 186 287 310 510 201 443 481 497 57 117 2 506 260 339 420 534 52 135 277 366 325 336 164 333 338 459 203 252 11 587 442 444 111 323 23 517 257 618 327 421 154 481 505 599 43 561 525 580 401 500 105 147 366 601 200 279 112 113 237 334 228 495 56 381 375 487 38 389 188 593 199 239 58 268 116 126 155 451 288 582 232 525 461 506 252 530 9 568 424 533 25 55 184 342 31 222 356 386 198 450 61 411 15 275 74 436 56 187 286 346 58 399 272 603 97 265 4 371 94 364 31 617 508 606 93 279 379 459 256 266 582 607 118 262 157 465 253 614 115 370 173 239 265 541 444 536 221 266 249 428 446 498 46 231 40 156 82 374 145 228 293 439 298 475 25 378 129 290 252 274 47 203 74 203 118 376 116 304 347 539 41 289 281 407 17 592 497 588 37 210 254 616 342 373 52 154 516 537 512 513 267 272 315 496 328 613 68 441 269 370 4 411 157 480 46 507 377 595 484 577 244 439 14 536 83 181 68 512 463 576 61 237 128 575 362 463 265 617 375 494 243 453 66 309 226 344 262 441 13 508 162 448 34 62 187 214 100 549 75 528 38 615 32 441 95 397 123 126 243 461 101 447 118 378 45 548 491 593 167 380 188 327 15 132 170 524 39 577 272 593 235 546 15 457 51 209 85 505 495 539 375 398 459 481 422 518 533 608 59 153 406 500 249 492 102 253 247 621 269 395 141 451 150 603 72 86 216 414 326 510 155 422 99 599 458 549 9 405 276 279 21 531 241 477 85 222 182 364 107 429 195 320 30 182 435 509 254 329 190 266 251 409 228 564 419 611 317 483 324 348 59 419 420 460 42 390 603 621 349 613 227 524 241 586 307 515 78 480 322 357 78 590 381 486 145 555 421 461 77 399 486 579 15 92 67 202 244 271 21 254 130 605 560 568 371 518 4 404 112 409 244 342 136 434 223 545 189 529 82 225 125 471 158 269 411 427 236 528 107 422 454 477 10 103 277 606 44 68 242 615 114 167 109 159 281 344 344 491 57 214 301 591 473 533 392 539 479 514 440 591 159 469 536 570 598 620 69 427 345 395 130 241 339 353 213 315 300 398 56 401 177 243 141 181 472 583 289 572 15 214 204 490 433 618 332 457 111 175 25 491 157 275 211 512 19 572 19 125 86 425 302 524 75 170 546 569 161 482 176 597 50 614 42 94 41 344 120 390 20 407 91 536 272 487 311 476 446 537 204 326 94 194 41 175 49 426 335 348 47 393 65 93 327 479 235 594 127 165 311 515 53 168 492 526 551 600 350 542 25 138 171 562 57 383 111 418 189 393 136 202 52 612 28 65 264 443 505 531 459 506 31 349 316 493 198 555 256 382 346 365 260 334 46 591 94 548 503 536 315 535 75 128 92 109 177 539 73 486 195 583 349 499 452 572 377 556 519 529 60 500 306 377 58 132 483 572 278 384 68 614 182 332 301 457 523 612 8 321 339 452 557 587 313 409 290 548 1 611 376 514 133 407 50 539 298 359 195 595 303 339 476 560 69 503 298 513 151 245 496 578 348 616 70 267 160 541 77 128 133 353 422 623 294 565 186 391 81 497 306 398 419 525 12 175 1 356 299 478 272 323 254 261 175 239 196 459 389 451 22 70 570 588 394 611 179 415 556 595 63 360 154 323 571 616 50 119 379 616 313 502 498 612 9 324 101 374 1 275 342 363 30 110 116 536 110 388 363 558 200 544 89 586 404 476 110 590 56 304 56 269 184 398 427 472 143 573 495 504 266 470 38 555 106 609 115 127 111 189 293 612 18 456 123 486 209 392 158 168 76 298 68 577 89 171 464 523 134 512 229 410 274 392 25 522 371 486 63 99 183 506 41 620 251 494 354 424 279 617 73 193 28 337 243 553 128 237 181 182 68 461 148 613 53 122 225 513 399 505 168 571 247 449 312 330 385 457 166 297 137 259 585 589 236 289 127 542 46 129 254 540 248 261 40 102 18 199 12 143 169 462 526 608 299 332 151 247 131 532 232 544 93 206 112 344 308 542 179 406 332 586 123 586 22 328 90 392 156 314 378 599 579 604 458 528 218 381 324 416 354 411 139 465 596 602 284 288 347 603 157 322 276 432 88 109 4 184 334 578 48 109 349 549 162 299 37 73 148 330 72 291 133 622 390 548 213 342 548 586 299 480 67 390 115 297 376 572 209 418 224 386 395 484 302 470 267 501 283 463 125 133 187 202 399 444 145 190 470 536 160 163 31 351 103 463 302 388 410 473 69 494 491 501 154 577 64 579 157 251 86 383 363 432 299 403 326 609 17 391 241 261 127 475 101 358 220 520 290 497 399 610 33 82 328 577 25 155 392 622 265 416 27 121 234 242 436 577 295 542 110 553 449 608 226 321 44 412 305 359 15 424 497 513 584 591 274 609 231 371 174 396 32 613 285 587 416 600 9 564 91 431 162 490 403 588 540 623 400 402 325 373 507 609 18 87 233 383 220 479 99 601 85 494 179 290 234 254 59 396 236 415 479 535 141 285 151 499 450 506 494 613 344 404 305 420 134 235 142 237 10 341 304 479 398 542 91 139 394 409 58 525 448 540 163 230 176 497 30 600 47 353 162 404 359 367 204 302 536 618 61 257 247 381 172 309 129 458 327 616 25 500 43 389 48 55 29 318 229 322 96 591 563 577 55 416 90 233 25 583 474 544 242 587 298 599 153 287 112 396 343 549 339 422 370 599 359 440 192 493 309 314 79 486 501 538 169 466 91 334 79 270 296 386 17 75 1 366 176 615 505 570 479 509 89 320 53 546 84 172 358 421 262 448 235 498 211 555 169 526 135 342 261 537 248 588 397 590 245 320 159 586 279 351 6 153 195 311 135 174 466 500 50 499 88 326 86 473 59 164 419 487 185 587 456 462 164 520 236 259 116 197 465 526 88 177 306 499 69 554 7 14 41 569 257 614 18 589 129 517 105 495 222 438 292 320 175 379 75 211 312 464 153 611 385 460 182 209 55 492 1 273 421 429 46 608 437 546 224 340 342 434 169 416 106 202 121 469 171 507 152 452 329 559 172 193 289 302 114 137 227 234 48 482 526 545 58 579 82 572 144 331 4 321 21 225 170 313 283 396 118 369 106 252 276 450 471 524 359 455 39 448 225 251 518 620 24 238 13 587 300 564 374 379 21 227 583 617 457 530 186 379 383 611 180 353 172 195 64 222 529 580 279 506 139 458 148 363 55 412 1 73 86 373 65 101 63 592 354 400 436 467 398 500 9 18 417 545 392 595 400 463 200 365 218 579 218 487 33 360 329 435 299 506 444 555 107 505 178 542 137 188 31 294 122 364 98 521 152 602 54 430 52 172 49 601 92 446 169 593 459 476 504 535 475 480 7 430 74 365 245 316 143 484 138 254 12 77 268 535 478 502 294 567 109 515 204 569 108 342 550 601 286 560 135 606 217 605 109 553 391 585 195 357 445 485 117 357 73 304 14 128 292 360 199 294 36 70 396 621 7 610 318 348 129 255 43 591 291 360 131 138 458 500 474 551 197 230 299 607 31 110 478 556 266 386 95 291 100 181 266 397 20 238 25 146 114 423 400 485 32 131 107 150 166 530 67 121 87 300 31 221 272 523 276 439 232 494 146 463 93 187 92 567 30 226 37 536 254 437 82 320 131 184 207 510 139 281 268 490 282 329 100 607 91 374 124 618 207 566 534 575 187 589 301 434 224 282 371 560 286 316 150 329 66 271 369 617 368 452 1 274 253 375 36 188 140 378 69 148 209 390 356 485 310 580 80 113 39 495 29 239 376 444 42 130 351 360 411 617 14 329 238 353 121 500 86 540 368 524 20 378 328 501 52 125 25 429 155 562 71 619 402 414 225 409 87 517 320 536 41 509 31 493 335 553 277 491 270 295 17 28 101 212 106 478 363 495 589 619 19 621 362 509 52 150 521 578 88 396 172 330 198 547 195 537 16 101 528 539 151 313 53 423 279 454 435 512 1 541 300 303 523 576 324 582 229 313 285 504 307 447 161 576 428 617 343 568 80 512 3 129 116 468 427 541 410 547 103 161 219 414 108 188 153 264 240 610 147 193 301 341 82 590 28 202 541 610 28 357 99 149 376 557 23 28 205 596 373 429 18 470 147 285 286 574 11 368 105 310 26 155 39 467 31 375 6 392 320 587 536 579 196 500 114 524 348 379 248 586 399 442 104 462 158 549 176 274 48 401 243 554 56 398 89 574 361 407 126 246 170 614 94 500 84 379 202 465 130 549 215 316 345 579 218 554 111 255 214 570 89 244 231 264 523 532 160 263 55 139 46 294 37 356 342 617 242 342 42 54 122 553 81 600 257 463 162 609 131 350 213 307 472 515 249 252 125 301 117 142 28 268 546 617 566 578 75 200 278 304 45 243 70 328 109 133 119 373 230 570 370 528 55 357 158 476 71 348 258 480 174 595 26 213 431 452 37 575 228 561 544 612 89 113 526 533 31 219 157 197 146 619 30 352 247 475 102 365 185 527 271 615 185 573 137 282 382 550 24 271 371 580 415 444 267 498 303 408 288 611 24 78 424 531 489 556 89 410 86 204 182 226 465 504 305 489 140 368 356 502 271 420 14 520 292 577 72 571 282 373 90 571 155 291 17 160 83 198 358 564 329 497 182 454 426 513 128 241 27 232 150 600 575 579 506 589 242 577 88 455 31 160 56 380 214 554 123 529 219 478 299 416 289 372 77 417 61 359 66 495 272 565 108 269 13 390 12 426 304 401 148 207 403 601 10 503 282 347 16 105 289 336 380 544 249 433 106 325 303 464 223 565 286 516 135 286 45 168 364 541 488 620 47 460 211 450 339 462 411 476 317 494 102 390 123 403 276 590 347 610 357 464 130 340 536 585 92 417 134 257 10 609 217 551 1 53 195 381 137 397 66 536 386 539 57 426 438 536 175 580 432 447 484 574 213 491 313 541 218 533 374 382 391 441 16 128 429 482 367 373 464 529 29 509 411 436 258 370 279 525 36 472 31 603 25 535 372 531 141 518 176 521 229 251 202 501 145 236 239 407 36 515 2 354 179 422 6 519 119 284 467 469 34 382 369 587 465 466 400 508 196 455 317 450 141 465 163 312 464 546 30 496 318 371 192 285 260 529 124 532 62 553 357 425 2 261 499 526 434 579 350 365 273 434 110 440 269 286 35 439 150 354 224 434 126 517 574 604 166 255 50 465 140 281 92 610 108 553 111 578 415 432 545 566 228 416 1 350 329 369 57 444 62 95 327 506 19 137 22 239 194 286 297 570 75 144 57 336 70 208 452 584 139 556 2 491 79 543 459 594 189 337 77 549 8 120 129 488 282 441 188 370 465 527 326 369 100 591 69 105 88 315 58 453 238 410 237 428 15 38 343 547 169 174 126 309 161 311 477 546 25 300 117 604 329 529 262 314 113 511 421 431 146 354 319 404 333 590 11 290 383 535 118 607 59 469 384 516 364 533 188 504 94 328 156 256 161 345 449 541 64 132 31 228 65 352 22 355 529 534 129 558 49 315 514 605 501 545 97 266 93 384 44 298 176 381 26 431 59 531 212 405 229 359 502 530 421 457 137 448 32 242 197 389 127 250 390 598 341 500 203 581 51 260 115 595 273 431 222 552 69 272 392 450 188 518 144 459 96 378 274 618 271 314 488 543 405 437 513 582 369 509 28 510 126 354 171 495 428 433 420 578 430 542 350 550 490 611 254 468 381 392 34 276 32 567 356 459 70 411 429 503 62 571 377 496 545 563 124 347 52 376 61 575 399 569 201 353 298 560 431 586 104 534 516 584 395 614 373 380 107 494 82 465 168 600 165 475 277 313 14 226 208 326 27 81 45 133 49 468 196 506 299 355 472 553 283 534 465 539 129 262 232 441 292 602 264 595 50 53 117 301 307 516 104 486 60 160 21 249 444 616 197 426 193 260 179 394 13 286 39 457 22 470 129 492 105 505 228 346 466 586 85 294 432 470 202 413 220 437 239 241 103 249 501 571 30 544 233 467 301 429 256 484 278 458 151 500 125 319 400 475 219 327 123 585 141 203 367 573 247 305 214 552 195 556 35 344 60 606 376 597 49 563 453 536 153 433 341 423 157 189 94 275 312 360 96 592 293 619 22 372 410 454 55 89
Output: 4

Example 3:

Input: 72 793 1 72 45 62 11 70 46 69 31 45 25 64 21 58 11 28 20 62 26 55 16 27 35 60 9 36 37 57 21 50 9 51 49 65 20 35 2 25 28 59 59 70 27 29 12 27 8 41 18 31 67 68 33 65 1 44 17 25 8 34 18 38 27 39 38 60 37 50 6 25 54 58 30 71 59 66 29 46 23 29 28 72 48 70 29 45 25 59 25 30 27 34 6 40 1 66 37 67 46 67 30 40 6 37 9 35 26 33 17 68 26 41 13 57 28 55 5 38 9 38 23 54 14 19 23 38 30 48 22 37 19 59 39 72 16 30 12 35 11 72 19 35 9 11 28 42 29 58 1 41 13 46 14 28 53 55 1 19 13 58 1 13 8 13 8 11 36 53 33 64 10 55 1 24 19 60 44 64 43 57 15 72 20 49 47 54 24 42 32 53 10 34 6 26 41 66 34 47 10 21 31 50 7 11 10 60 2 54 3 43 10 36 19 28 14 62 11 22 21 33 38 47 58 62 53 63 2 26 49 54 39 49 22 27 9 33 2 17 30 63 55 72 2 36 15 26 44 70 32 34 30 69 12 45 44 49 41 50 10 25 10 72 2 13 28 63 26 69 16 45 7 32 31 67 2 39 14 57 20 65 21 62 1 53 62 72 55 64 52 67 10 62 17 49 32 62 52 56 42 62 9 61 8 35 14 27 45 51 6 42 3 19 45 58 8 44 62 68 39 45 6 32 28 69 11 62 16 34 7 24 20 37 36 67 38 68 48 63 9 54 35 67 51 63 7 9 35 51 14 29 32 55 21 55 4 11 38 46 26 29 29 36 14 52 10 12 65 72 6 72 21 29 7 44 41 55 50 55 16 46 27 28 12 39 15 39 26 39 10 48 2 18 3 30 17 28 38 42 6 56 16 42 13 71 5 47 1 10 18 40 31 43 17 27 19 23 3 49 19 38 7 66 31 66 21 70 12 50 14 40 8 61 23 58 12 14 2 14 21 56 8 20 3 5 11 15 42 49 24 65 60 70 21 57 61 65 19 50 23 72 13 35 4 28 56 65 30 64 10 33 46 48 22 62 9 10 11 14 62 70 27 59 9 72 29 59 31 61 17 69 37 64 44 53 49 60 38 55 1 61 27 71 42 53 63 66 49 58 15 27 42 58 13 29 29 62 10 38 54 72 43 66 48 71 39 55 12 22 37 39 13 49 2 69 25 46 38 59 1 47 6 9 63 70 50 63 21 64 26 61 48 54 7 20 18 52 7 12 11 71 30 70 4 5 1 15 64 66 17 23 15 36 26 51 4 21 6 69 46 56 8 56 17 26 10 47 24 63 3 4 10 69 21 32 65 69 24 35 1 11 24 64 17 67 45 66 37 52 40 59 18 69 10 13 9 62 23 59 20 68 23 32 32 60 16 70 11 55 28 52 33 61 61 64 7 47 3 45 8 57 43 52 45 52 32 54 43 53 24 31 49 67 20 44 18 57 33 39 16 49 10 52 26 27 4 46 16 23 32 35 48 62 7 71 45 48 11 26 39 61 15 34 23 41 42 54 42 66 64 67 35 53 5 28 2 47 6 36 24 52 15 16 26 31 6 55 29 49 16 52 9 39 52 68 44 51 5 22 44 67 44 47 8 54 3 53 25 48 4 37 16 20 32 41 1 25 3 61 9 17 3 60 25 55 38 49 12 72 37 53 14 49 25 33 20 64 19 57 4 53 47 59 13 15 37 41 14 39 40 42 20 61 47 62 2 35 8 38 3 69 11 63 48 52 63 67 26 32 4 26 49 71 8 21 6 57 19 63 14 42 14 50 5 11 18 64 8 17 34 54 1 6 42 70 34 36 26 36 5 44 14 71 27 41 15 18 27 70 23 67 62 66 20 55 1 45 34 59 1 28 6 19 20 59 19 40 2 6 14 67 7 40 30 47 4 43 22 54 69 72 19 66 14 22 26 30 7 21 35 68 44 65 1 38 17 55 4 29 5 18 46 66 29 42 8 63 22 70 44 58 34 71 5 33 7 14 15 41 2 21 21 67 8 53 37 49 58 59 15 59 2 9 40 51 41 59 41 60 9 40 59 62 39 47 24 47 31 64 3 16 26 35 40 56 5 32 32 43 27 49 22 23 3 29 15 21 53 56 18 58 51 66 14 65 40 57 10 32 20 24 26 59 30 32 34 49 13 60 15 51 2 40 34 62 53 58 1 71 63 64 13 20 40 64 17 35 1 17 56 66 36 41 8 31 30 35 28 70 11 57 12 49 4 57 2 24 21 25 4 61 12 59 57 68 3 63 19 42 32 36 44 66 44 62 29 35 32 63 6 67 1 7 5 12 11 41 20 31 1 14 64 69 32 56 1 4 26 70 5 72 13 38 54 63 43 54 7 46 19 54 33 56 5 21 22 52 9 52 40 60 43 64 14 20 37 56 10 20 1 52 39 60 42 55 21 49 28 49 37 58 46 58 18 19 5 10 55 59 12 64 1 46 6 58 11 45 26 49 18 28 42 51 23 31 6 54 4 12 4 47 45 54 33 71 3 6 32 65 15 70 8 71 17 57 40 69 7 64 71 72 39 53 42 68 14 33 5 70 5 50 10 50 5 56 3 23 24 66 2 62 29 64 28 65 65 71 34 69 33 38 18 39 33 34 1 40 3 65 7 10 37 38 23 62 48 55 31 57 23 37 36 65 10 26 7 29 29 65 7 19 21 71 27 68 3 42 18 25 26 34 4 31 39 57 51 53 22 40 1 18 36 38 23 48 33 53 6 20 1 27 7 56 51 72 36 54 8 42 19 51 52 64 31 33 3 72 23 57 6 17 21 26 9 16 59 68 38 64 13 31 33 41 11 17 15 44 37 63 43 62 25 49 33 68 5 8 26 58 50 61 5 34 11 60 19 45 13 59 25 42 41 67 44 68 2 16 29 50 17 54 8 29 50 67 21 68 12 56 36 43 43 48 10 61 39 41 1 60 22 55 5 27 22 59 9 27 31 69 44 60 25 31 7 30 15 57 28 54 19 64 12 62 28 34 2 34 12 34 58 63 29 61 15 31 33 69 15 29 44 59 23 36 28 40 11 43 33 67 55 69 1 29 21 63 6 46 62 69 25 54 47 69 42 47 12 43 38 51 6 22 21 59 3 25 43 55 14 63 18 54 62 71 3 57 22 41 15 55 46 64 3 55 59 60 4 15 24 37 5 7 31 41 8 27 24 39 44 52 17 32 19 69 37 71 22 68 34 57 38 52 32 50 61 62 18 65 3 8 34 67 42 43 63 72 34 48 66 71 40 49 36 57 38 66 52 66 42 57 9 44 5 45 7 45 25 32 6 30 18 41 15 28 8 15 5 25 6 53 23 34 14 56 19 29 23 28 6 35 30 51 52 69 28 60 11 36 47 55 57 58 27 46 18 49 18 22 6 27 42 48 26 43 16 51 44 54 58 70 6 34 13 61 9 48 10 45 8 52 37 60 16 38 53 66 5 64 34 44 21 65 2 5 40 72 7 18 1 56 31 49 1 34 20 67 29 33 8 40 13 47 16 58 39 59 8 43 37 43 33 37 50 57 10 43 6 63 10 41
Output: 2

Constraints:

1 <= n <= 1176; 0 <= m <= 2352.

Loading...
Test Cases:No test cases
No test cases available.
The Fewest Hops of Brasshaven - MEDIUM Coding Problem | CodeTikki