12 16 8 9 3 2 3 3 3 3 4 3 3
 1000 1000 
 4 80 906 142 1000 0 1000 0 700
 5 80 906 0 700 0 508 484 1000 142 1000
 3 738 312 1000 624 500 566
 4 614 312 346 0 476 0 738 312
 5 614 312 738 312 500 566 234 0 346 0
 3 242 754 0 508 500 566
 4 378 754 608 1000 484 1000 242 754
 5 378 754 242 754 500 566 712 1000 608 1000
 5 608 624 500 566 1000 624 1000 1000 862 1000
 4 608 624 862 1000 712 1000 500 566
 6 234 342 0 108 0 0 234 0 500 566 300 450
 4 234 342 300 450 0 276 0 108
 4 196 508 0 406 0 276 300 450
 5 196 508 300 450 500 566 0 508 0 406
 3 1000 252 1000 624 476 0
 3 476 0 1000 0 1000 252
 3 426 0 1000 0 1000 248
 3 356 1000 0 1000 0 562
 5 210 206 0 174 0 0 426 0 412 200
 5 210 206 412 200 356 1000 0 562 0 174
 3 426 0 1000 248 1000 518
 4 500 148 412 200 426 0 590 148
 4 500 148 590 148 384 600 412 200
 5 590 148 1000 518 1000 1000 356 1000 384 600
 5 162 314 0 362 0 0 568 0 284 314
 4 162 314 284 314 0 628 0 362
 4 284 314 568 0 1000 0 1000 380
 3 0 628 284 314 1000 380
 3 300 1000 0 1000 0 628
 5 770 652 1000 900 1000 1000 566 1000 250 566
 4 770 652 250 566 1000 380 1000 900
 5 250 736 420 1000 300 1000 0 628 250 566
 4 250 736 250 566 566 1000 420 1000
 4 626 0 1000 0 1000 1000 428 1000
 5 72 714 156 1000 0 1000 0 0 626 0
 4 72 714 626 0 428 1000 156 1000
 3 704 0 1000 0 1000 162
 5 1000 162 1000 1000 0 1000 0 0 704 0
 5 868 168 1000 440 1000 1000 348 1000 450 0
 4 868 168 450 0 1000 0 1000 440
 4 348 1000 0 1000 0 0 450 0
 6 724 200 806 0 1000 0 1000 1000 408 1000 386 450
 4 724 200 386 450 368 0 806 0
 4 408 1000 0 1000 0 0 368 0
 4 78 916 120 1000 0 1000 0 880
 5 78 916 0 880 0 532 232 1000 120 1000
 5 0 532 0 0 1000 0 1000 1000 232 1000
 3 1000 810 1000 1000 598 1000
 4 768 810 1000 348 1000 810 598 1000
 6 768 810 598 1000 0 1000 0 0 1000 0 1000 348
 5 672 732 1000 772 1000 1000 0 1000 0 840
 5 672 732 0 840 0 452 1000 608 1000 772
 5 332 188 0 324 0 0 1000 0 1000 436
 5 332 188 1000 436 1000 608 0 452 0 324
 4 446 0 1000 0 1000 1000 384 1000
 5 216 290 198 1000 0 1000 0 0 276 0
 5 216 290 276 0 446 0 384 1000 198 1000
 3 516 1000 0 1000 0 402
 4 638 602 1000 360 1000 1000 516 1000
 6 638 602 516 1000 0 402 0 0 1000 0 1000 360