Pająki

Limit pamięci: 32 MB

Bajtockie pająki przędą sieci w bardzo specyficzny sposób. Każda sieć leży w jednej płaszczyźnie, a oka sieci są trójkątami. Pająk rozpoczyna budowę sieci od pojedynczego oka-trójkąta. Żeby rozbudować sieć, pająk wybiera zewnętrzną nić (czyli taką, która nie jest wspólnym bokiem dwóch ok-trójkątów), snuje z jej końcowych węzłów dwie nici, które następnie zlepia w nowym węźle na zewnątrz dotychczas zbudowanej sieci. Poza swoimi końcami, nowe nici nie mają żadnych innych wspólnych punktów z dotychczasową siecią.

Arachnolodzy postanowili sklasyfikować bajtockie pająki ze względu na rodzaje budowanych sieci. W tym celu zorganizowali wyprawę do największej puszczy w Bajtocji. Zadaniem uczestników wyprawy jest zebranie opisów napotkanych sieci. Pojedynczy opis jest tworzony w następujący sposób. Badacz numeruje w dowolny sposób węzły sieci kolejnymi liczbami naturalnymi, poczynając od 1, a następnie zapisuje liczbę węzłów i pary numerów tych węzłów, które są końcami poszczególnych nici. Zauważmy, że w -węzłowej pajęczynie jest dokładnie nici. Po powrocie z wyprawy arachnolodzy mają zamiar pogrupować opisane sieci na sieci podobne. Dwie sieci są podobne, jęsli mają taką samą liczbę węzłów i jeśli można tak przenumerować węzły jednej z nich, że jej poszczególne nici łączą węzły o dokładnie takich samych numerach co nici w sieci drugiej. Napisz program, który usprawni pracę arachnologów.

Twój program powinien wczytać liczbę par sieci do zbadania i dla każdej z nich:

wczytać opisy dwóch sieci,
sprawdzić, czy są one podobne,
zapisać wynik.

Wejście

W pierwszym wierszu dana jest liczba całkowita równa liczbie par sieci do zbadania, . W nastęnych wierszach podane są opisy badanych par sieci. Opis każdej pary sieci składa się z czterech wierszy.

Pierwszy z tych wierszy zawiera jedną liczbę całkowitą (, ), równą liczbie węzłów w pierwszej sieci.

Drugi wiersz zawiera liczb całkowitych oddzielonych pojedynczymi spacjami. Są to końce wszystkich nici w pierwszej sieci. Liczby i , na pozycjach i (, , ), są końcami jednej, tej samej nici.

Trzeci wiersz zawiera jedną liczbę całkowitą (), równą liczbie węłów w drugiej sieci.

Czwarty wiersz zawiera liczb całkowitych, oddzielonych pojedynczymi odstępami. Są to końce wszystkich nici w drugiej sieci. Liczby i , na pozycjach i (, , , są końcami jednej, tej samej nici.

Wyjście

Dla każdej pary badanych sieci, w kolejności zgodnej z kolejnością pojawiania się ich opisów na wejściu, należy wypisać dokładnie jeden wiersz, zawierający słowo:

TAK - gdy sieci są podobne,
NIE - w przeciwnym przypadku.

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

TAK
NIE

<Wyślij rozwiązanie> [0/100]