스파이

시간 제한3초메모리 제한512 MB

요약

각 스파이 k가 스파이 a_k를 감시하는 함수 그래프가 주어질 때, S의 모든 원소가 S 밖의 스파이에게 감시받는 최대 부분집합 S의 크기를 구한다.

난이도: 보통10점 중 7점
유형: 그래프, 그리디, 동적 계획법
정답자: 아직 제출이 없습니다

문제

어느 정보기관은 $n$ 명의 스파이를 고용하고 있다. 각 스파이는 정확히 다른 한 명의 스파이를 감시한다. 이 감시 관계는 고정되어 있으며, 스파이 $k$ 는 스파이 $a_k$ 를 감시한다( $a_k \ne k$ ).

기관은 비밀 작전에 최대한 많은 스파이를 투입하려고 한다. 단, 작전에 참여하는 모든 스파이는 작전에 참여하지 않는 스파이 중 적어도 한 명에게 감시받아야 한다. (감시 관계는 바뀌지 않는다.)

다음을 수행하는 프로그램을 작성하시오.

각 스파이가 누구를 감시하는지에 대한 정보를 표준 입력에서 읽는다.
작전에 참여하는 모든 스파이가 작전에 참여하지 않는 스파이 중 적어도 한 명에게 감시받도록 할 때, 작전에 투입할 수 있는 스파이의 최대 수를 계산한다.
결과를 표준 출력에 쓴다.

입력

첫째 줄에 스파이의 수 $n$ 이 주어진다( $2 \le n \le 10^6$ ). 스파이는 $1$ 번부터 $n$ 번까지 번호가 매겨져 있다. 이어지는 $n$ 개의 줄에는 각 스파이가 누구를 감시하는지가 주어진다. $k+1$ 번째 줄에는 하나의 정수 $a_k$ 가 주어지며, 이는 스파이 $k$ 가 스파이 $a_k$ 를 감시함을 뜻한다( $1 \le k \le n$ , $1 \le a_k \le n$ , $a_k \ne k$ ).

출력

첫째 줄에 작전에 투입할 수 있는 스파이의 최대 수를 하나의 정수로 출력한다.

힌트

예제2

예제 1
입력
```
6
2
3
1
3
6
5
```
예상 출력
```
3
```
예제 2
입력
```
2
2
1
```
예상 출력
```
1
```