12 15 9 6 4 3 3 4 4 3 4 3 2
 1000 1000 
 3 698 0 1000 0 1000 220
 3 378 0 698 0 1000 220
 3 492 844 450 1000 316 1000
 6 492 844 316 1000 0 1000 0 730 560 844 450 1000
 3 378 0 1000 220 400 526
 4 48 176 0 78 0 0 280 0
 5 48 176 280 0 378 0 0 308 0 78
 4 378 308 0 662 0 308 108 220
 6 378 308 108 220 378 0 400 526 0 730 0 662
 5 958 844 676 1000 450 1000 780 532 912 592
 5 958 844 912 592 1000 632 1000 1000 676 1000
 5 982 532 780 532 1000 220 1000 632 912 592
 3 982 532 912 592 780 532
 4 780 532 560 844 0 730 400 526
 3 400 526 1000 220 780 532
 4 76 82 0 216 0 0 234 0
 5 76 82 234 0 560 0 0 450 0 216
 4 610 148 834 0 1000 0 1000 228
 6 610 148 1000 228 1000 394 336 180 560 0 834 0
 3 1000 394 1000 1000 514 1000
 3 514 1000 336 180 1000 394
 3 0 450 336 180 514 1000
 4 98 680 322 1000 0 1000 0 914
 5 98 680 0 914 0 450 514 1000 322 1000
 3 1000 762 1000 1000 406 1000
 3 354 0 1000 0 1000 294
 4 406 1000 0 1000 0 608 1000 294
 3 1000 294 1000 762 406 1000
 3 354 0 1000 294 0 608
 3 0 608 0 0 354 0
 4 754 724 1000 576 1000 1000 456 1000
 7 754 724 456 1000 0 1000 0 598 338 0 1000 0 1000 576
 4 56 320 272 0 338 0 130 368
 5 56 320 130 368 0 598 0 0 272 0
 4 714 810 1000 804 1000 1000 850 1000
 5 714 810 850 1000 340 1000 1000 648 1000 804
 5 340 1000 0 1000 0 0 1000 0 1000 648
 4 644 0 1000 0 1000 1000 452 1000
 4 596 218 0 284 0 0 162 0
 6 596 218 162 0 644 0 452 1000 0 1000 0 284
 5 924 704 870 0 1000 0 1000 1000 760 1000
 5 924 704 760 1000 550 1000 576 0 870 0
 4 478 90 0 740 0 0 576 0
 5 478 90 576 0 550 1000 0 1000 0 740
 4 90 892 130 1000 0 1000 0 704
 5 90 892 0 704 0 648 218 1000 130 1000
 5 772 604 694 0 1000 0 1000 1000 218 1000
 5 772 604 218 1000 0 648 0 0 694 0
 4 56 534 380 0 1000 0 1000 570
 7 56 534 1000 570 1000 1000 0 1000 0 386 184 0 380 0
 3 0 386 0 0 184 0
 4 702 970 780 1000 460 1000 730 864
 5 702 970 730 864 1000 728 1000 1000 780 1000
 4 460 820 1000 380 1000 728 730 864
 7 460 820 730 864 460 1000 0 1000 0 0 1000 0 1000 380
 4 564 176 1000 550 1000 1000 784 1000
 6 564 176 784 1000 542 1000 516 0 1000 0 1000 550
 4 542 1000 0 1000 0 0 516 0
 4 1000 392 1000 1000 0 1000 0 500
 4 0 500 0 0 1000 0 1000 392