Znajdz algorytmem wlaczania heurystyke dla problemu komiwojazera. Wierzcholki nazywamy liczbami naturalnymi zaczynajac od 1. W kroku wyboru nalezy zawsze wybierac najdalszy od dotychczas wybranej sciezki wierzcholek. Zaczynamy od wierzcholka 1. Kazdy kolejny wierzcholek wstawiamy w pierwsze wolne miejsce, dla ktorego dlugosc nowego cyklu jest minimalna.

Wejscie

Pierwsza linia wejscia zawiera liczbe testow. Dla kazdego testu dany jest jeden graf, opisany nastepujaco:
pierwsza linia bloku zawiera liczbe wierzcholkow grafu, nastepne n linii macierz sasiedztwa tego grafu. Wiersze i kolumny opisuja wierzcholki w kolejnosci rosnacej.

t [liczba testow]
[dla kazdego przypadku testowego:]
n [liczba wierzcholkow]
0 a b ... x
a 0 c ... y
b c 0 ... z
... ... ...
x y z ... 0

Wyjscie

Dla kazdego przypadku testowego kolejne rozwiazania czesciowe, czyli n linii formatu:
l[chwilowa minimalna dlugosc cyklu]: a b c [ciag wierzcholkow]

Kolejne przypadki testowe rozdziela pusta linia

Przyklad

Wejscie:
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 

Wyjscie:
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