C - Diamond Collector

Autor: Bartosz Nowierski

Jasiu znalazł na swoim twardym dysku starą grę o wdzięcznej nazwie "Diamond Collector". Gra jest bardzo prymitywna. Polega na tym, że ludzik chodzi po planszy złożonej z kwadratowych pól ułożonych w jednej linii (taka jednowymiarowa szachownica) i zbiera na niej diamenty. Gra składa się z kilku rund. Runda polega na tym, że na planszy są rozłożone diamenty; gdy ludzik dojdzie do jednego z nich zabiera go, po czym znikają z planszy wszystkie diamenty i zaczyna się nowa runda z nowymi diamentami (gdy w nowej rundzie pojawi się diament na polu, na którym stoi ludzik to jest on automatycznie zabierany i od razu zaczyna się kolejna runda). Chodzi o to, żeby przejść wszystkie rundy wykonując jak najmniej kroków (krok - przejście z jednego pola na pole sąsiednie).

Gra ma kilka poziomów, każdy z nich oferuje inną planszę i inny rozkład diamentów w rundach. Ludzik zaczyna każdy poziom stojąc na polu o numerze 1, mając 0 zebranych diamentów i 0 wykonanych kroków (niezależnie od tego co się działo na poprzednich poziomach).
Niestety w czasach, w których gra powstałą nie wynaleziono jeszcze generatorów liczb pseudolosowych więc poziomy mają z góry określony wygląd. Jasiu grając w tę grę wiele razy zdołał poznać ją na wylot i potrafi przejść każdy poziom w najmniejszej możliwej liczbie kroków.

Zadanie

Napisz program, który powie ile kroków wykona Jasiu na danym poziomie gry (przy założeniu, że gra optymalnie).

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita d, oznaczająca liczbę poziomów gry, a następnie opisane są te poziomy.
W pierwszym wierszu opisu poziomu znajdują się dwie liczby całkowite N i M (1<=N<=500, 1<=M<=500), oznaczających odpowiednio liczbę pól na planszy i liczbę rund. Potem następuje M wierszy z opisem kolejnych rund. Opis rundy zaczyna się od liczby n (1<=n<=N), po której znajduje się n różnych (posortowanych rosnąco) liczb całkowitych z zakresu od 1 do N, oznaczających numery pól, na których znajdują się diamenty (pola numerowane są poczynając od 1).

Wyjście

Twój program powinien zapisać na wyjściu d liczb całkowitych, każdą w osobnym wierszu. Liczba w i-tym wierszu ma oznaczać liczbę kroków potrzebnych Jasiowi do przejścia i-tego poziomu.

Przykład

Dla wejścia:

3
2 3
1 2
2 1 2
1 1
3 3
1 3
1 2
1 1
5 4
2 2 5
3 1 3 5
1 4
5 1 2 3 4 5

2
4
3