Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

EXPLO - Eksplozja

Dzień 6.XII.2003 w Megabajtolandii zaczął się cicho i spokojnie jak każdy inny dzień. Ludzie spacerują po chodnikach, niektórzy idą do pracy, inni do szkoły, jeszcze inni do sklepu po bułki. Kierowcy tradycyjnie stoją w korkach, popijając kawę i czytając gazetę za kierownicą. Nagle cała ta regularność dnia została zaburzona przez ogromną eksplozję. “Wysadzili ambasadę Bajtocji!!!” - ktoś krzyknął. Wszyscy w popłochu zaczęli uciekać.

Policja w Megabajtolandii działa bardzo sprawnie i pierwsze radiowozy pojawiły się przy ambasadzie już po paru sekundach. Zatrzymano wszystkie osoby, które były w pobliżu miejsca zdarzenia w momencie eksplozji - część z nich to sprawcy, ale część to mogą być zwykli przechodnie - świadkowie zdarzenia. Podczas przesłuchań każdy z zatrzymanych wskazał dokładnie jednego sprawcę, przy czym wiadomo, że tylko osoby niewinne zawsze mówią prawdę (bo niby czemu miałyby kłamać?). Natomiast sprawcy chcą utrudnić pracę policji, więc niektórzy wskazują osoby niewinne, a niektórzy swoich współpracowników (lub nawet siebie).

Policjanci mają w takiej sytuacji twardy orzech do zgryzienia. Muszą aresztować pewną grupę potencjalnych sprawców (bo media im nie dadzą spokoju), ale trudno im z takich danych wywnioskować kto naprawdę jest winny. Istnieje wiele grup potencjalnych winnych, takich że nie ma sprzeczności (w sensie warunków opisanych powyżej) w zeznaniach zatrzymanych. Na dobrą sprawę każda z tych grup może być równie dobra, jak i równie zła. Policjanci chcąc zminimalizować liczbę niewinnych aresztowanych zdecydowali się na wybranie grupy o najmniejszej możliwej liczności.

Zadanie

Dla podanej liczby zatrzymanych osób oraz zeznań każdej z nich Twój program powinien podać ile osób zostanie aresztowanych.

Specyfikacja wejścia

W pierwszej linii wejścia znajduje się jedna dodatnia liczba całkowita, oznaczająca liczbę zestawów testowych, które dalej pojawią się na wejściu. Każdy zestaw ma następującą postać. W pierwszej linii znajduje się jedna liczba całkowita N (2 ≤ N ≤ 100.000), która oznacza liczbę osób zatrzymanych w pobliżu ambasady (osoby ponumerowane są od 1 do N). W liniach od 2 do N+1 zestawu znajduje się jedna liczba całkowita z przedziału od 1 do N. Liczba w i+1 linii zestawu mówi na kogo wskazał i-ty człowiek podczas przesłuchania.

Specyfikacja wyjścia

Dla każdego zestawu danych pojawiającego się na wejściu należy wypisać dokładnie jedną liczbę całkowitą (każdą w osobnej linii), oznaczającą liczbę osób, które zostaną aresztowane.

Przykład

Wejście

2
3
2
3
1
4
2
3
2
2

Wyjście

2
1

Dodane przez:adrian
Data dodania:2005-11-26
Limit czasu wykonania programu:0.455s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:MWPZ 2003

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.