Sparing w Programowaniu Zespołowym Politechnika Poznańska, 13.03.2004

Opis

Zadanie dotyczy słynnej łamigłówki, znanej pod nazwą Wieże z Hanoi. Otóż mamy trzy pionowo stojące pręty oraz zestaw N krążków, z których każdy ma inną wielkość określoną przez liczbę ze zbioru {1,2,...,N}. Na początku wszystkie krążki są nałożone, w kolejności rosnących wielkości (1 na górze, N na dole), na pręt pierwszy. Mamy do dyspozycji ruch polegający na przełożeniu dokładnie jednego krążka z góry pewnego pręta na górę jakiegokolwiek innego pręta, przy czym nie wolno w żadnym momencie położyć większego krążka na mniejszy. Należy przełożyć wszystkie krążki z pręta o numerze 1 na pręt o numerze 3, z użyciem jak najmniejszej liczby ruchów. Można przy tym wykorzystywać pomocniczo pręt o numerze 2. Przełożenie krążków nazywany optymalnym, jeżeli liczba ruchów w nim wykonana jest najmniejsza z możliwych. Istnieje dokładnie jedno przełożenie optymalne.

Zadanie

Mając dane pewne ułożenie krążków na prętach (spełniające założenie, że krążki są położone na prętach w kolejności rosnących wielkości), należy sprawdzić, czy taka konfiguracja mogła wystąpić w optymalnym przekładaniu i jeśli tak, to podać numer ruchu, po którym wystąpi.

Specyfikacja wejścia

W pierwszym wierszu wejścia podana jest dodatnia liczba całkowita D (1 ≤ D ≤ 30), oznaczająca liczbę zestawów testowych, które dalej pojawią się na wejściu. W pierwszym wierszu każdego zestawu danych znajduje się jedna liczba całkowita N (1 ≤ N ≤ 5.000), oznaczająca liczbę przekładanych krążków. W kolejnych trzech wierszach znajdują się opisy ułożeń krążków na kolejnych prętach: w i-tym jako pierwsza występuje jedna liczba całkowita k_i (z przedziału od 0 do N) oznaczająca liczbę krążków na danym pręcie, po której występuje k_i liczb całkowitych, oddzielonych spacjami, ze zbioru {1,2,...,N}, oznaczających wielkości krążków leżących na danym pręcie (podane są w kolejności rosnącej). Każdy z N krążków występuje w zestawie dokładnie raz.

Specyfikacja wyjścia

Dla każdego zestawu należy wypisać w osobnym wierszu albo jedną liczbę całkowitą, będącą numerem ruchu, po którym podana w zestawie konfiguracja zostanie osiągnięta, albo jedno słowo "NIE", jeżeli nie może ona wystąpić w optymalnym przekładaniu.

Przykład

2
3
2 2 3
0
1 1
2
1 1
1 2
0

1
NIE