문제
마피아 게임은 잘 알려진 게임이다. 정올 캠프를 비롯하여 학생들이 캠프에 갔을 때 늦은 밤 모여 앉아 하는 게임 중 하나이기도 하다. ^^
이 문제를 풀기 위하여 마피아 게임의 규칙을 모두 알 필요는 없다. 단지 마피아는 누가 누구인지 모두 알고 평민은 누가 누구인지 전혀 모른다는 것만 알면 된다. 또한 마피아는 게임을 하는 동안 자신이 평민인척 한다.
게임이 진행 중 인데 현재 N명이 남아 있고 각 사람이 어느 한 사람만을 지목하여 마피아라고 말할 수 있다. 그런데 평민은 추측하여 지목하는 것이고 마피아는 평민인 척 하면서 평민을 마피아로 지목한다. 마피아는 마피아를 지목하는 일이 없고 평민은 누구든 지목할 수 있다. 어느 한 사람이 여러 번 지목될 수 있다.
마피아가 누구인지는 모르지만 마피아로 지목된 사람에 대한 정보를 알고 있다고 할 때, 현재 남은 N명의 사람중에서 마피아는 최대 몇 명으로 추측 할 수 있는지 구하는 프로그램을 작성하시오.
마피아가 누구인지 정답을 구하는 것이 아니라 주어진 데이터로 추측할 수 있는 마피아의 최대인원을 구한다는 것에 유의한다.
입력
>첫 행에 현재 남은 인원 수 N( 2 ≤ N ≤ 500,000)이 입력된다.
게임에 참여중인 사람의 번호는 1 ~ N이다. 이 후 N개의 행에 걸쳐 Ai가 입력되는데 Ai는 i번째 사람으로부터 마피아라고 지목 받은 사람이 Ai라는 의미이다.
출력
마피아로 추측되는 최대 인원은 몇 명인지 출력한다.
<입력 예 1에 대한 설명>
마피아는 2와 3이 될 수 있다.
<입력 예 2에 대한 설명>
셋 중에 누구든 마피아가 될 수 있지만 가능한 최대 인원은 1명이다.
예를 들어 1번이 마피아라고 할 경우 2번은 평민이다. 3번이 마피아라면 1번을 마피아라고 지목할 수 없으므로 평민이다.
예제1
입력
3
2
1
1
출력
2
예제2
입력
3
2
3
1
출력
1
예제3
입력
7
3
3
4
5
6
4
4
출력
4
출처
COCI 2014/2015 contest1 4