← 返回题目列表

Codeforces · 2033/E

E. 樱子、小介和排列

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

樱子的考试结束了,她的成绩非常好。作为奖励,她收到了排列 $$$p$$$。小介并不完全满意,因为他没有通过一次考试,也没有收到礼物。他决定潜入她的房间(感谢她的锁密码)并破坏排列,使其变得简单。

如果对于每个 $$$i$$$ $$$(1\le i \le n)$$$ 满足以下条件之一,则排列 $$$p$$$ 被认为是简单的:

- $$$p_i=i$$$
- $$$p_{p_i}=i$$$

例如,排列 $$$[1, 2, 3, 4]$$$、$$$[5, 2, 4, 3, 1]$$$ 和 $$$[2, 1]$$$ 很简单,而 $$$[2, 3, 1]$$$ 和 $$$[5, 2, 1, 4, 3]$$$ 则不然。

在一次操作中,Kosuke 可以选择索引 $$$i,j$$$ $$$(1\le i,j\le n)$$$ 并交换元素 $$$p_i$$$ 和 $$$p_j$$$。

樱子即将回家。你的任务是计算 Kosuke 需要执行的最少运算次数才能使排列变得简单。

输入

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

每个测试用例由两行描述。

- 第一行包含一个整数 $$$n$$$ ($$$1\le n \le 10^6$$$) — 排列 $$$p$$$ 的长度。
- 第二行包含 $$$n$$$ 整数 $$$p_i$$$ ($$$1\le p_i\le n$$$) — 排列 $$$p$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。

保证 $$$p$$$ 是一个排列。

输出

对于每个测试用例,输出 Kosuke 为使排列简单而需要执行的最少操作数。

示例

输入 #1

6
5
1 2 3 4 5
5
5 4 3 2 1
5
2 3 4 5 1
4
2 3 4 1
3
1 3 2
7
2 3 1 5 6 7 4

输出 #1

0
0
2
1
0
2

注意

在第一个和第二个示例中,排列已经很简单。

在第四个示例中,交换 $$$p_2$$$ 和 $$$p_4$$$ 就足够了。因此,在 $$$1$$$ 运算中,排列将变为 $$$[2, 1, 4, 3]$$$。