The Thorny Path

题意翻译

给定一个大小为$n$的排列$P$，你可以任意交换排列中的两个元素若干次，要求在最大化 交换后的排列 的各个置换环的大小的乘积的情况下，最小化交换元素的次数

题目描述

According to a legend the Hanoi Temple holds a permutation of integers from $ 1 $ to $ n $ . There are $ n $ stones of distinct colors lying in one line in front of the temple. Monks can perform the following operation on stones: choose a position $ i $ ( $ 1 \le i \le n $ ) and cyclically shift stones at positions $ i $ , $ p[i] $ , $ p[p[i]] $ , .... That is, a stone from position $ i $ will move to position $ p[i] $ , a stone from position $ p[i] $ will move to position $ p[p[i]] $ , and so on, a stone from position $ j $ , such that $ p[j] = i $ , will move to position $ i $ . Each day the monks must obtain a new arrangement of stones using an arbitrary number of these operations. When all possible arrangements will have been obtained, the world will end. You are wondering, what if some elements of the permutation could be swapped just before the beginning? How many days would the world last? You want to get a permutation that will allow the world to last as long as possible, using the minimum number of exchanges of two elements of the permutation. Two arrangements of stones are considered different if there exists a position $ i $ such that the colors of the stones on that position are different in these arrangements.

输入输出格式

输入格式

Each test consists of multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \leq t \leq 10^3 $ ). Description of the test cases follows. The first line of each test case contains $ n $ ( $ 3 \leq n \leq 10^6 $ ). The next line contains $ n $ integers $ p_1, \dots, p_n $ ( $ 1 \le p_i \le n $ ). It is guaranteed that $ p $ is a permutation. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^6 $ .

输出格式

For each of the $ t $ test cases, print two integers on a new line: the largest possible number of days the world can last, modulo $ 10^9 + 7 $ , and the minimum number of exchanges required for that.

输入输出样例

输入样例 #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

说明

Let's label the colors of the stones with letters. Explanations for the first two test cases of the first example: 1. Using the permutation $ [2, 3, 1] $ , we can additionally obtain the arrangements CAB and BCA from ABC. This is already the maximum possible result. 2. Using the permutation $ [2, 1, 3] $ , the only BAC can be obtained from ABC. As we saw in the previous case, two arrangements are not the maximum possible number of distinct arrangements for $ n = 3 $ . To get an optimal permutation, for example, we can swap $ 1 $ and $ 3 $ , so we will get the permutation $ [2, 3, 1] $ .