← 返回题目列表

Codeforces · 1411/F

F. 荆棘之路

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

根据传说,河内寺庙拥有从 $$$1$$$ 到 $$$n$$$ 的整数排列。寺庙前有一排颜色各异的石头。武僧可以对棋子进行如下操作:选择一个位置$$$i$$$ ($$$1 \le i \le n$$$),循环移动$$$i$$$、$$$p[i]$$$、$$$p[p[i]]$$$、...的棋子,即$$$i$$$位置的棋子会移动到$$$p[i]$$$位置,$$$p[i]$$$位置的棋子会移动到$$$p[i]$$$位置。 $$$p[i]$$$ 将移动到位置 $$$p[p[i]]$$$,依此类推,从位置 $$$j$$$ 开始的石头,使得 $$$p[j] = i$$$ 将移动到位置 $$$i$$$。

僧侣们每天必须使用任意数量的这些操作来获得新的石头排列。当所有可能的安排都完成时,世界就结束了。您想知道,如果可以在开始之前交换排列的某些元素会怎样?世界还能持续多少天?

您希望使用排列中两个元素的最少交换次数来获得一个排列,使世界能够尽可能长久地持续下去。

如果存在 $$$i$$$ 位置,使得该位置上的棋子颜色在这些排列中不同,则认为两种棋子排列不同。

输入

每个测试由多个测试用例组成。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 10^3$$$)。测试用例的描述如下。

每个测试用例的第一行包含 $$$n$$$ ($$$3 \leq n \leq 10^6$$$)。下一行包含 $$$n$$$ 整数 $$$p_1, \dots, p_n$$$ ($$$1 \le p_i \le n$$$)。保证 $$$p$$$ 是一个排列。

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

输出

对于每个 $$$t$$$ 测试用例,在新行中打印两个整数:世界可以持续的最大可能天数,以 $$$10^9 + 7$$$ 为模,以及所需的最小交换次数。

示例

输入 #1

3
3
2 3 1
3
2 1 3
3
1 2 3

输出 #1

3 0
3 1
3 2

输入 #2

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

输出 #2

4 0
4 1
4 0
4 1
4 2

注意

让我们用字母来标记石头的颜色。第一个示例的前两个测试用例的说明:

1. 利用排列$$$[2, 3, 1]$$$,我们还可以从ABC得到排列CAB和BCA。这已经是最大可能的结果了。
2. 利用排列$$$[2, 1, 3]$$$,可以从ABC得到唯一的BAC。正如我们在前面的例子中看到的,对于 $$$n = 3$$$,两种排列并不是不同排列的最大可能数量。例如,为了获得最佳排列,我们可以交换 $$$1$$$ 和 $$$3$$$,因此我们将得到排列 $$$[2, 3, 1]$$$。