← 返回题目列表

Codeforces · 1969/A

A. 两个朋友

中文机器翻译题面 查看原题

Monocarp 想要举办一个派对。他有 $$$n$$$ 个朋友,并且他希望至少有 $$$2$$$ 的朋友参加他的聚会。

第 $$$i$$$ 位朋友最好的朋友是 $$$p_i$$$。所有 $$$p_i$$$ 都是不同的,并且对于每个 $$$i \in [1, n]$$$,$$$p_i \ne i$$$。

Monocarp 可以向朋友发送邀请。如果第 $$$i$$$ 位朋友和第 $$$p_i$$$ 位朋友均收到邀请,则第 $$$i$$$ 位朋友将参加聚会(请注意,第 $$$p_i$$$ 位朋友不必实际参加聚会)。每份邀请都会发送给其中一位朋友。

例如,如果 $$$p = [3, 1, 2, 5, 4]$$$,并且 Monocarp 向好友 $$$[1, 2, 4, 5]$$$ 发送邀请,则好友 $$$[2, 4, 5]$$$ 将参加聚会。朋友 $$$1$$$ 不会来,因为他最好的朋友没有收到邀请;朋友$$$3$$$不会来,因为他没有收到邀请。

计算 Monocarp 必须发送的最少邀请数量,以便至少 $$$2$$$ 朋友来参加聚会。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5000$$$) — 测试用例的数量。

每个测试用例由两行组成:

- 第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 50$$$) — 好友数量;
- 第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$; $$$p_i \ne i$$$; 所有 $$$p_i$$$ 都是不同的)。

输出

打印一个整数 — Monocarp 必须发送的最少邀请数。

示例

输入 #1

3
5
3 1 2 5 4
4
2 3 4 1
2
2 1

输出 #1

2
3
2

注意

在第一个测试用例中,Monocarp 可以向好友 $$$4$$$ 和 $$$5$$$ 发送邀请。两人都会来参加聚会,因为他们是彼此最好的朋友,而且两人都收到了邀请函。

例如,在第二个测试用例中,Monocarp 可以向好友 $$$1、2$$$ 和 $$$3$$$ 发送邀请。那么朋友 $$$1$$$ 和 $$$2$$$ 将参加:朋友 $$$1$$$ 和他最好的朋友 $$$2$$$ 有邀请,朋友 $$$2$$$ 和他最好的朋友 $$$3$$$ 有邀请。朋友 $$$3$$$ 不会参加,因为他的朋友 $$$4$$$ 没有邀请。不可能向少于 $$$3$$$ 的朋友发送邀请,而至少有 $$$2$$$ 来。

在第三个测试用例中,Monocarp 可以向好友 $$$1$$$ 和 $$$2$$$ 发送邀请,他们都会参加。