POLSKI SPOJ

Znajdź algorytmem włączania heurystykę dla problemu komiwojażera. Wierzchołki nazywamy liczbami naturalnymi zaczynając od 1. W kroku wyboru należy zawsze wybierać najdalszy od dotychczas wybranej ścieżki wierzchołek. Zaczynamy od wierzchołka 1. Każdy kolejny wierzchołek wstawiamy w pierwsze wolne miejsce, dla którego długość nowego cyklu jest minimalna.

Wejście

Pierwsza linia wejścia zawiera liczbę testów. Dla każdego testu dany jest jeden graf, opisany następująco:
pierwsza linia bloku zawiera liczbę wierzchołków grafu, następne n linii macierz sąsiedztwa tego grafu. Wiersze i kolumny opisują wierzchołki w kolejności rosnącej.

t [liczba testów]
[dla każdego przypadku testowego:]
n [liczba wierzchołków]
0 a b ... x
a 0 c ... y
b c 0 ... z
... ... ...
x y z ... 0

Wyjście

Dla każdego przypadku testowego kolejne rozwiazania częściowe, czyli n < 150 linii formatu:
l[chwilowa minimalna długość cyklu]: a b c [ciąg wierzchołków]

Kolejne przypadki testowe rozdziela pusta linia

Przykład

Wejście:
2
5
0 11 16 28 42 
11 0 44 31 27 
16 44 0 06 15 
28 31 06 0 21 
42 27 15 21 0 
4
0 83 15 35 
83 0 73 56 
15 73 0 51 
35 56 51 0 

Wyjście:
0: 1 
84: 1 5 
91: 1 4 5 
87: 1 4 5 2 
81: 1 3 4 5 2 

0: 1 
166: 1 2 
174: 1 4 2 
179: 1 4 2 3