Rak n Roll

Witaj w zespole!

Pozwól, że od razu przejdę do rzeczy. Nasze repozytorium Git zawiera n gałęzi. Każda gałąź poza główną została utworzona z innej znajdującej się w repozytorium. Oznacza to, że nasze repozytorium ma strukturę drzewa.

Twój poprzednik miał za zadanie przygotować listę wszystkich par gałęzi rodzic dziecko oznaczających, że gałąź dziecko została utworzona bezpośrednio z gałęzi rodzic. Niestety zamiast przeczytać dokładnie treść zadania wolał chyba skonsultować się w tej sprawie z wróżbitą Maciejem, bo zrobił coś zupełnie innego.

Dostarczył nam spis wszystkich gałęzi z naszego repozytorium, w którym przy każdej gałęzi wypisane są wszystkie gałęzie znajdujące się w jej poddrzewie. Szczerze mówiąc to nie mamy pewności czy jego spis faktycznie odpowiada poprawnej strukturze drzewa, musisz to sam sprawdzić.

Twoim zadaniem jest odtworzenie drzewa na podstawie informacji dostarczonych przez Twojego poprzednika, a następnie przygotowanie listy par gałęzi rodzic dziecko.

Wejście

W pierwszej linii wejścia podana jest liczba gałęzi w repozytorium n ∈ [2, 1000]. W kolejnych n liniach znajdują się opisy gałęzi.

Opis każdej gałęzi zawarty jest w jednej linii. Rozpoczyna się on od podania jej nazwy oraz liczby gałęzi znajdujących się w jej poddrzewie. Następnie podane są nazwy tych gałęzi. Gwarantujemy, że liczba gałęzi w poddrzewie nie przekracza n-1, zaś ich nazwy nie powtarzają się.

Nazwy gałęzi składają się z małych liter alfabetu angielskiego, cyfr oraz znaku podkreślenia. Ich długość nie przekracza 10 znaków.

Wyjście

Jeżeli informacje dostarczone przez Twojego poprzednika odpowiadają poprawnej strukturze drzewa i udało Ci się je odtworzyć to w pierwszej linii wyjścia należy wypisać słowo TAK. Następnie w kolejnych n-1 liniach należy podać pary gałęzi w formacie rodzic dziecko. Kolejność wypisania par jest dowolna.

W przeciwnym wypadku należy wypisać słowo NIE.

Przykład 1

Wejście:

13
iss_6 0
bgfx_2_1 0
goal_2 1 iss_4
bgfx_2_2 0
iss_4 0
goal_3 2 iss_6 iss_5
bgfx_3_1 0
iss_2 2 bgfx_2_2 bgfx_2_1
iss_3 1 bgfx_3_1
iss_5 0
release_1 12 iss_6 iss_1 iss_3 goal_1 iss_2 bgfx_3_1 goal_2 bgfx_2_2 goal_3 bgfx_2_1 iss_4 iss_5
iss_1 0
goal_1 6 bgfx_2_1 iss_1 bgfx_3_1 iss_3 iss_2 bgfx_2_2

Wyjście:

TAK
goal_3 iss_6
iss_2 bgfx_2_1
release_1 goal_2
goal_2 iss_4
iss_2 bgfx_2_2
release_1 goal_3
goal_3 iss_5
iss_3 bgfx_3_1
goal_1 iss_2
goal_1 iss_3
goal_1 iss_1
release_1 goal_1

Przykład 2

Wejście:

7
master 6 feature_1 feature_2 iss_1 iss_2 iss_3 iss_4
feature_1 2 iss_1 iss_2
feature_2 2 iss_3 iss_4
iss_1 0
iss_2 0
iss_3 0
iss_4 0

Wyjście:

TAK
master feature_1
master feature_2
feature_1 iss_1
feature_1 iss_2
feature_2 iss_3
feature_2 iss_4

Przykład 3

Wejście:

3
fix_1 2 fix_2 fix_3
fix_3 0
fix_2 1 fix_1

Wyjście:

NIE