Problem10395--参加会议的最多员工数

10395: 参加会议的最多员工数

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

一个公司准备组织一场会议,邀请名单上有 $n$ 位员工。公司准备了一张圆形的桌子,可以坐下任意数目的员工。
员工编号为 $0$ 到 $n-1$。每位员工都有一位喜欢的员工,每位员工当且仅当他被安排在喜欢员工的旁边,他才会参加会议。每位员工喜欢的员工不会是他自己。
给你一个下标从 0 开始的整数数组 favorite,其中 favorite[i] 表示第 $i$ 位员工喜欢的员工。请你返回参加会议的最多员工数目。

Input

第一行包括两个整数 $n\ (2\leq n \leq 5\times 10^5)$。
第二行 $n$ 个整数,第 $i$ 个表示 favorite[i]。

Output

一个整数,参加会议的最多员工数目。

Sample 1 Input

4
2 2 1 2

Sample 1 Output

3

上图展示了公司邀请员工 0,1 和 2 参加会议以及他们在圆桌上的座位。
没办法邀请所有员工参与会议,因为员工 2 没办法同时坐在 0,1 和 3 员工的旁边。
注意,公司也可以邀请员工 1,2 和 3 参加会议。 所以最多参加会议的员工数目为 3。

Sample 2 Input

5
3 0 1 4 1

Sample 2 Output

4

上图展示了公司可以邀请员工 0,1,3 和 4 参加会议以及他们在圆桌上的座位。 员工 2 无法参加,因为他喜欢的员工 1 旁边的座位已经被占领了。 所以公司只能不邀请员工 2 。 参加会议的最多员工数目为 4 。

Sample 3 Input

3
1 2 0

Sample 3 Output

3
每个员工都至少是另一个员工喜欢的员工。所以公司邀请他们所有人参加会议的前提是所有人都参加了会议。 座位安排同图 1 所示: 
- 员工 0 坐在员工 2 和 1 之间。 
- 员工 1 坐在员工 0 和 2 之间。 
- 员工 2 坐在员工 1 和 0 之间。
参与会议的最多员工数目为 3 。

HINT

Source/Category