Problem D: Imperium Uhid

Treść

Dawno, bardzo dawno temu, na wodach nieprzemierzonego oceanu Uhub, istniało potężne imperium Uhid. Kraj swym zasięgiem obejmował niezliczoną liczbę wysp i wysepek. Ze względu na swój wyspiarski charakter, głównym środkiem komunikacyjnym imperium były statki. Niestety ze względu na brak dokładnych map i dobrze usytuowanych portów, kapitanowie nie mieli łatwego zadania. Musieli lawirować pomiędzy wyspami, często zdając się tylko na swą intuicję. Imperator Umass Piąty postanowił zmienić tę jakże niekorzystną sytuację. Sprowadził zza oceanu najlepszych kartografów by ci sporządzili szczegółowe mapy jego włości. Teraz Jego Wysokość pragnie wyznaczyć najkrótsze morskie trasy pomiędzy każdą parą wysp, a na ich końcach zbudować porty. Pomóż mu w tym zadaniu. Napisz program, który na podstawie mapy stworzonej przez kartografów obliczy szukane trasy.

Podczas tworzenia mapy imperium Uhid przyjęto następujące zasady. Cały obszar, zarówno morski jak i lądowy, został podzielony na jednakowe kwadraty. Następnie każdy z nich został zakwalifikowany jako woda, jeżeli większą jego część zajmuje ocean i jako ląd w przeciwnym wypadku. Jako wyspę uznano taki fragment lądu, dla którego można przejść pomiędzy dowolnymi kwadratami poruszając się w kierunku północnym, południowym, wschodnim, bądź zachodnim. Podobny model poruszania się przyjęto dla statków. Statki swą podróż zaczynają i kończą na lądzie, podróżując po oceanie w czterech wyżej wymienionych kierunkach. Może się zdarzyć, że pomiędzy niektórymi parami wysp nie istnieje tak zdefiniowane połączenie. Z drugiej strony, z każdego punktu oceanu można dopłynąć na kraniec imperium Uhid, czyli do jednego z brzegów mapy.

Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=20) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych

Pierwszy wiersz zestawu danych zawiera dwie liczby całkowite n i m (1<=n,m<=300), oddzielone spacją, oznaczające odpowiednio liczbę wierszy i kolumn mapy. W kolejnych n wierszach podany jest rysunek mapy. Każdy wiersz składa się dokładnie z m znaków: . (kropek) bądź * (gwiazdek). Kropka oznacza, że dany kwadrat mapy jest sklasyfikowany jako ocean, gwiazdka natomiast symbolizuje ląd. Na mapie znajdują się nie mniej niż 2 i nie więcej niż 100 wysp.

Wyjście

Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu jest ciąg liczb całkowitych oddzielonych pojedynczymi spacjami, reprezentujący długości wszystkich wyznaczonych tras, uporządkowanych niemalejąco. Długość trasy pomiędzy jedną parą wysp wystarczy wypisać raz, gdyż odległość od dowolnej wyspy A do B jest zawsze taka sama jak od B do A.

Przykład

dane wejściowe:
1
9 8
**..*.*.
***.*...
....*...
.***....
........
..******
********
.......*
**......

wynik:
2 2 2 2 2 2 3 5 5 6 13