12 15 9 8 4 3 3 2 2 3 4 4 3
 1000 1000 
 3 0 438 0 0 648 0
 4 644 948 1000 862 1000 1000 724 1000
 5 644 948 724 1000 508 1000 1000 762 1000 862
 3 940 400 1000 308 1000 528
 6 940 400 1000 528 432 146 648 0 1000 0 1000 308
 5 70 438 0 550 0 438 216 292 108 492
 4 70 438 108 492 0 692 0 550
 3 1000 528 1000 762 508 1000
 3 432 146 1000 528 754 764
 4 426 292 432 146 754 764 216 292
 3 426 292 216 292 432 146
 3 754 764 508 1000 344 1000
 3 216 292 754 764 344 1000
 5 42 932 0 878 0 692 216 292 280 646
 5 42 932 280 646 344 1000 0 1000 0 878
 4 96 694 190 1000 0 1000 0 538
 5 96 694 0 538 0 392 394 1000 190 1000
 4 812 64 808 0 1000 0 1000 110
 5 812 64 1000 110 1000 284 664 0 808 0
 3 1000 638 1000 1000 790 1000
 5 832 440 560 0 664 0 1000 284 1000 516
 5 832 440 1000 516 1000 638 348 0 560 0
 5 394 1000 0 392 0 0 348 0 1000 638
 3 1000 638 790 1000 394 1000
 3 0 302 0 0 402 0
 4 260 668 274 1000 0 1000 0 588
 5 260 668 0 588 0 302 616 1000 274 1000
 3 616 1000 0 302 402 0
 3 402 0 1000 0 1000 328
 3 616 1000 402 0 1000 328
 4 976 692 788 1000 616 1000 784 706
 5 976 692 784 706 1000 328 1000 1000 788 1000
 4 958 840 794 1000 638 1000 1000 734
 4 958 840 1000 734 1000 1000 794 1000
 6 660 486 398 1000 0 1000 0 0 1000 0 1000 316
 5 660 486 1000 316 1000 734 638 1000 398 1000
 3 490 0 1000 0 1000 188
 5 664 606 204 1000 0 1000 0 0 490 0
 5 664 606 490 0 1000 188 1000 1000 204 1000
 5 438 0 1000 0 1000 1000 0 1000 0 638
 4 236 162 0 182 0 0 256 0
 5 236 162 256 0 438 0 0 638 0 182
 5 476 0 1000 0 1000 1000 0 1000 0 452
 3 0 452 0 0 476 0
 5 256 0 1000 0 1000 1000 0 1000 0 468
 3 0 468 0 0 256 0
 4 902 92 1000 266 1000 442 690 0
 4 902 92 690 0 1000 0 1000 266
 5 1000 442 1000 1000 0 1000 0 0 690 0
 4 780 884 1000 488 1000 1000 560 1000
 4 780 884 560 1000 1000 372 1000 488
 5 644 354 136 1000 0 1000 0 0 734 0
 6 644 354 734 0 1000 0 1000 372 560 1000 136 1000
 4 552 500 1000 856 1000 1000 690 1000
 6 552 500 690 1000 434 1000 542 0 1000 0 1000 856
 4 486 310 298 1000 0 1000 0 358
 6 486 310 0 358 0 0 542 0 434 1000 298 1000
 5 456 0 1000 0 1000 1000 0 1000 0 274
 4 138 80 0 130 0 0 130 0
 5 138 80 130 0 456 0 0 274 0 130