Polish version    English version  
  Historia OI -> XI OI 2003/2004 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
III Etap
Przepisy
Dla zawodnikow
Przydatne zasoby
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
XI Olimpiada Informatyczna 2003/2004

Zadanie: szp

Szpiedzy

Zawody I stopnia  
Plik źródłowy: szp.xxx (xxx=pas,c,cpp)
Limit pamięci: 32 MB

Bajtocka Agencja Wywiadowcza ma w swoich szeregach szpiegów. Każdy szpieg w ramach obowiązków służbowych śledzi dokładnie jednego, innego szpiega.

Król Bajtazar chce powierzyć tajną misję jak największej liczbie szpiegów. Misja jest jednak na tyle ważna, że każdy szpieg biorący w niej udział musi być śledzony przez przynajmniej jednego szpiega nie biorącego udziału w misji (przydział obowiązków związanych ze śledzeniem szpiegów nie ulega zmianie).

Zadanie

Napisz program, który:

  • wczyta ze standardowego wejścia opis tego, którzy szpiedzy śledzą których,
  • obliczy, ilu maksymalnie szpiegów można wysłać z tajną misją tak, aby każdy z nich był śledzony przez przynajmniej jednego szpiega nie biorącego udziału w misji,
  • wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia zapisano jedną dodatnią liczbę całkowitą n - liczbę szpiegów, 2 <= n <= 1000000. Szpiedzy są ponumerowani od 1 do n. W kolejnych n wierszach opisano kogo śledzi każdy ze szpiegów. W każdym z tych wierszy znajduje się po jednej dodatniej liczbie całkowitej. Liczba ak znajdująca się w wierszu o numerze k + 1 oznacza, że szpieg numer k śledzi szpiega numer ak, 1 <= k <= n, 1 <= ak <= n, ak <> k.

Wyjście

Twój program powinien wypisać w pierwszym wierszu wyjścia jedną liczbę całkowitą - maksymalną liczbę szpiegów, których można wysłać z tajną misją.

Przykład

Dla danych wejściowych:

6
2
3
l
3
6
5

poprawnym wynikiem jest:

3

Przykład




Wersja do druku