Mozaikowatość [B]

Limit pamięci: 64 MB

Biolodzy molekularni od dawna badają genomy (czyli sekwencje genów) różnych organizmów, usiłując na ich podstawie wysnuć wnioski dotyczące ewolucji gatunków, a także działania komórek i tkanek. Podczas tych badań m.in. porównują poszczególne geny pod względem budowy i funkcji i utożsamiają ze sobą geny bardzo podobne do siebie (tzw. geny homologiczne).

Ostatnio, badając wirusy atakujące bakterie (zwane bakteriofagami lub po prostu fagami), zaobserwowali bardzo intrygujące zjawisko. Jeśli mianowicie ustawić sekwencje genów niektórych fagów jedne pod drugimi i pokolorować homologiczne geny tą samą barwą, to uzyskuje się swoistą mozaikę:

Do opisu zjawiska, które odkryli, naukowcy wymyślili miarę, którą nazwali współczynnikiem mozaikowatości. Współczynnik ten można wyznaczyć dla danego faga tylko w zestawieniu z innymi fagami - jest nim wtedy łączna liczba punktów obliczona następująco. Za każde dwa geny z faga -tego oraz za każde dwa różne fagi , takie że:

• gen ma gen homologiczny w fagu -tym i nie ma genu homologicznego w fagu -tym,
• gen ma gen homologiczny w fagu -tym i nie ma genu homologicznego w fagu -tym,

W sytuacji przedstawionej na rysunku fag numer ma współczynnik mozaikowatości równy Jest tak, ponieważ gen niebieski ma gen homologiczny w fagu i nie ma genu homologicznego w fagu ; z kolei gen pomarańczowy ma gen homologiczny w fagu i nie ma genu homologicznego w fagu . Analogiczna sytuacja ma miejsce dla genów brązowego i pomarańczowego. Natomiast fag numer ma współczynnik mozaikowatości równy - dostaje punkty za pary genów: czerwony-niebieski, czerwony-brązowy, 2 razy żółty-niebieski i 2 razy żółty-brązowy.

Ręczne wyznaczanie współczynników nie jest proste, więc biolodzy postanowili poprosić Cię o napisanie programu, który policzy współczynniki mozaikowatości wszystkich podanych fagów.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opisy par homologicznych genów w grupie fagów,
• policzy współczynniki mozaikowatości dla wszystkich fagów
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita () oznaczająca liczbę fagów, które należy rozważyć.

W -tym z następnych wierszy znajduje się opis sekwencji genów -tego faga. Każdy taki opis składa się z jednej liczby całkowitej () oznaczającej liczbę genów w sekwencji -tego faga, po której następuje liczb całkowitych () opisujących kolejne jego geny. Wszystkie te liczby są pooddzielane pojedynczymi odstępami.

Dwa geny uważamy za homologiczne wtedy i tylko wtedy, gdy w opisie na wejściu są im przypisane te same numery. Naukowcy dowiedli, że żadne dwa geny jednego faga nie mogą być homologiczne (W praktyce wystąpienie dwóch homologicznych genów u jednego faga jest mało prawdopodobne.), a zatem w opisie żadnego faga nie może się pojawić dwukrotnie ta sama liczba.

Wyjście

Wyjście powinno składać się z wierszy. W -tym z nich powinna znajdować się jedna liczba, równa współczynnikowi mozaikowatości -tego faga.

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

6
3
2
1

Rysunek z treści zadania jest ilustracją dla testu przykładowego.

Autor zadania: Aleksander Mielczarek.