← 返回题目列表

Codeforces · 1855/A

A. 道尔顿老师

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

Dalton 是一个班级的老师,该班级有 $$$n$$$ 名学生,编号从 $$$1$$$ 到 $$$n$$$。教室里有 $$$n$$$ 椅子,编号也从 $$$1$$$ 到 $$$n$$$。最初,学生 $$$i$$$ 坐在椅子 $$$p_i$$$ 上。保证 $$$p_1,p_2,\dots, p_n$$$ 是长度 $$$n$$$ 的排列。

如果学生的号码与他/她的椅子的号码不同,他/她会很高兴。为了让所有的学生都高兴,道尔顿可以重复执行以下操作:选择两个不同的学生并交换他们的椅子。最少需要多少步才能让所有学生都满意?可以证明,在这个问题的约束下,有可能通过有限数量的动作让所有学生都满意。

长度 $$$n$$$ 的排列是一个数组,由 $$$n$$$ 个从 $$$1$$$ 到 $$$n$$$ 的不同整数以任意顺序组成。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 学生人数。

第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — $$$p_i$$$ 表示学生 $$$i$$$ 的初始主席。保证 $$$p$$$ 是一个排列。

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

输出

对于每个测试用例,输出所需的最小移动次数。

示例

输入 #1

5
2
2 1
3
1 2 3
5
1 2 5 4 3
4
1 2 4 3
10
10 2 1 3 6 5 4 7 9 8

输出 #1

0
2
2
1
1

注意

在第一个测试用例中,两个学生都已经很高兴,因此 Dalton 可以执行 $$$0$$$ 动作。

在第二个测试用例中,Dalton 可以交换学生 $$$1$$$ 和 $$$2$$$ 的椅子,得到数组 $$$[2, 1, 3]$$$。然后他可以交换学生 $$$2$$$ 和 $$$3$$$ 的椅子来得到数组 $$$[2, 3, 1]$$$。此时所有的学生都高兴了,他表演了$$$2$$$动作。用更少的动作来完成任务是不可能的。

在第三个测试用例中,通过交换学生 $$$1$$$ 和 $$$2$$$ 的椅子,然后交换学生 $$$4$$$ 和 $$$5$$$ 的椅子,Dalton 在 $$$2$$$ 移动中得到数组 $$$[2, 1, 5, 3, 4]$$$。