12 15 10 8 3 3 3 3 3 4 2 4 2
 1000 1000 
 4 216 152 0 212 0 0 298 0
 5 216 152 298 0 404 0 0 414 0 212
 3 448 400 404 0 1000 550
 4 578 850 642 1000 514 1000 492 800
 6 578 850 492 800 470 600 1000 802 1000 1000 642 1000
 4 470 600 448 400 1000 550 1000 802
 3 0 414 404 0 470 600
 3 470 600 514 1000 0 414
 4 860 104 810 0 1000 0 1000 166
 5 860 104 1000 166 1000 216 728 0 810 0
 6 626 124 1000 410 1000 550 404 0 728 0 932 162
 4 626 124 932 162 1000 216 1000 410
 3 180 1000 0 1000 0 746
 5 130 746 0 528 0 414 514 1000 264 1000
 5 130 746 264 1000 180 1000 0 746 0 528
 3 0 372 0 0 358 0
 4 902 80 942 0 1000 0 1000 210
 5 902 80 1000 210 1000 524 726 0 942 0
 3 666 1000 0 1000 0 670
 4 120 576 222 780 0 670 0 510
 5 120 576 0 510 0 372 444 890 222 780
 6 356 526 1000 796 1000 1000 666 1000 444 890 360 792
 7 356 526 360 792 132 526 358 0 726 0 1000 524 1000 796
 4 106 372 0 372 358 0 132 526
 3 106 372 132 526 0 372
 4 174 960 102 1000 0 1000 0 928
 5 174 960 0 928 0 750 290 1000 102 1000
 4 972 964 944 1000 744 1000 872 890
 5 972 964 872 890 1000 780 1000 1000 944 1000
 3 0 456 0 0 484 0
 3 788 0 1000 0 1000 294
 3 242 228 484 0 788 0
 8 788 0 1000 294 1000 780 744 1000 290 1000 0 750 0 456 242 228
 5 502 0 1000 0 1000 1000 0 1000 0 356
 4 130 120 0 260 0 0 82 0
 5 130 120 82 0 502 0 0 356 0 260
 6 360 218 674 0 1000 0 1000 1000 0 1000 0 530
 5 360 218 0 530 0 218 520 0 674 0
 3 0 218 0 0 520 0
 5 658 0 1000 0 1000 1000 0 1000 0 552
 4 86 402 0 194 0 0 168 0
 5 86 402 168 0 658 0 0 552 0 194
 3 720 0 1000 0 1000 634
 4 634 744 0 658 0 0 720 0
 6 634 744 720 0 1000 634 1000 1000 0 1000 0 658
 3 538 0 1000 0 1000 212
 4 182 824 450 1000 0 1000 0 388
 7 182 824 0 388 0 0 538 0 1000 212 1000 1000 450 1000
 4 826 636 1000 206 1000 1000 546 1000
 5 826 636 546 1000 552 0 1000 0 1000 206
 5 406 774 232 1000 0 1000 0 0 258 0
 5 406 774 258 0 552 0 546 1000 232 1000
 4 1000 426 1000 1000 0 1000 0 340
 4 0 340 0 0 1000 0 1000 426
 4 968 172 888 0 1000 0 1000 236
 5 968 172 1000 236 1000 334 634 0 888 0
 6 634 492 1000 758 1000 1000 0 1000 0 0 634 0
 4 634 492 634 0 1000 334 1000 758
 4 1000 642 1000 1000 0 1000 0 362
 4 0 362 0 0 1000 0 1000 642