30429번 - Reavers

문제

시이가 연 하이퍼-스타게이트를 통해, 외계인들이 지구를 침략하려고 한다! 이 외계인들은 리버(파괴자)와 스캐럽(갑충탄) 중 하나이다. 이들은 각각 인간 사회에 교묘하게 숨어들어, 동호의 집을 날려버리려고 한다. 동호는 자신의 집을 지키기 위해 인간 사회에 숨어든 리버와 스캐럽의 수를 알아내고자 한다.

이를 위해 동호는 외계인으로 의심되는 사람들을 1ドル$번부터 $N$번까지 총 $N$명 두고, 각 사람에게 다른 사람의 정체를 들었다. $N$명 중에는 진짜 사람이 최소 한 명은 존재한다.

$i$번 사람은 $A_i$번 사람의 정체가 진짜 사람이라고 답하거나 외계인이라고 말했다. $i$번 사람은 $A_i$번 사람의 정체를 알고 있다.

• $i$번 사람이 진짜 사람일 경우
  • $A_i$번 사람이 진짜 사람이라면 진짜 사람이라고, 외계인이라면 외계인이라고 주장한다.
• $i$번 사람이 리버였을 경우
  • $A_i$번 사람은 항상 진짜 사람이며, $A_i$번 사람이 외계인이라고 주장한다.
• $i$번 사람이 스캐럽이였을 경우
  • $A_i$번 사람은 항상 외계인이며, $A_i$번 사람이 진짜 사람이라고 주장한다.

동호는 내심 외계인의 수가 적기를 바라고 있기 때문에 이들의 답변이 주어졌을 때 가능한 외계인의 최소 수를 구하고 싶다. 동호를 도와 가능한 외계인의 최소 수를 구하라!

입력

첫 번째 줄에 사람의 수 $N$이 주어진다.

그다음 $N$개 줄에 1ドル$번 사람부터 $N$번 사람까지 각 사람에게 들은 다른 사람의 정체가 한 줄에 하나씩 순서대로 주어진다. 그중 $i$번째 줄에는 $i$번 사람이 정체를 말한 사람의 번호 $A_i$가 주어지고, 이어서 $A_i$번 사람이 외계인임을 주장하면 1, 진짜 사람임을 주장하면 0이 공백을 사이에 두고 주어진다.

출력

첫 번째 줄에 $N$명 중 외계인이 최소 얼마나 있는지를 출력한다.

제한

• 1ドル \le N \le 100,000円$
• 1ドル \le A_i \le N$

힌트