31414번 - 주둔

문제

운전병 해찬이의 활약 덕분에 A국은 B국과의 전쟁에서 승리할 수 있었다. 그러나 A국 역시 전쟁으로 인해 큰 피해를 입었기 때문에, A국은 언제 침략해 올지 알 수 없는 B국에 대비하기 위해 군대를 재정비하려고 한다.

A국에는 $N$개의 지역이 있으며, 전쟁으로 인해 무너진 교통망을 복구하기 위해 각 지역에서 다른 지역으로 향하는 양방향 도로를 하나씩 지었다. 그중 $i$번째 지역에서 지은 도로는 $d_i$번째 지역으로 이동할 수 있는 양방향 도로이다.

또한 B국의 침략에 대비하기 위해 각 지역에 부대를 주둔시키려고 하는데, 부대를 불필요하게 많이 주둔시키면 효용성이 감소하므로 효용성이 최대가 되도록 부대를 각 지역에 효율적으로 배치하고자 한다. 이때, 부대의 효용성은 해당 부대에서 하나의 도로만 거쳐서 이동할 수 있는 지역들 중 부대를 주둔시키지 않은 서로 다른 지역의 개수로 정의한다.

각 부대들의 효용성의 합이 최대가 되게 부대를 배치했을 때의 효용성의 합을 구해주자.

입력

첫 번째 줄에 지역의 개수 $N$이 주어진다. $(2 \le N \le 100,000円)$

두 번째 줄에 각 지역에서 지은 양방향 도로와 연결된 지역을 의미하는 $N$개의 정수 $d_1, \cdots, d_N$이 공백으로 구분되어 주어진다. $(1 \le d_i \le N;$ $d_i \neq i)$

출력

모든 부대의 효용성의 합의 최댓값을 출력한다.

제한

힌트