W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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:
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.
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:
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