Codah ClubTrain. Submit. Improve.
Sign in
English
#00002E

ministri

After successfully finishing the parliament elections, the government needs to be formed. There are N (1<=N<=30000) candidates for ministers- all competent people willing to contribute to the government's success. All of the candidates are friends, and each of them has a best friend where the feeling is not necessarily mutual.


In order to form an efficient government, it is necessary to choose as many ministers as possible, but also to make sure that every minister is the best friend of at least one member of the parliament.


Your task is to write a program that forms the largest government that fulfills the given conditions.


InputThe first line of the standard input contains a number N, which is the number of candidates for ministers. The next N lines describe the friendships among the candidates. Number j in line i+1 represents the best friend of the i-th minister.

OutputThe first and only line of standard output should contain the largest number of ministers that can form the government.

Input:
6
3
6
2
4
1
3
Output:
4
Explanation:
Candidates 2, 3, 4 and 6 will form the government. Candidate 2 is the best friend of candidate 3, candidate 3 is the best friend of candidate 6, candidate 6 is the best friend of candidate 2, and candidate 4 is his own best friend (if you look closely, nobody said this is not possible).

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.