The Thorny Path
Contest: Technocup 2021 - Elimination Round 3
Difficulty rating: 3000
Tags: greedy, math

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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]$$$.

Example input:
3
3
2 3 1
3
2 1 3
3
1 2 3

Example output:
3 0
3 1
3 2

Example input:
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

Example output:
4 0
4 1
4 0
4 1
4 2

Editorial:
The problem boils down to getting an array consisting of threes and a remainder (2 or 2+2 or 4) using split and merge operations. It helps to think that all merge operations are done before split operations.
To solve the problem, you can brute which elements of the array the remainder is subtracted from, then the rest of the operations are done greedily.
Bonus. Given $$$k$$$. We need to get an array consisting of $$$k$$$ using these operations. Assume that the sum of the array elements is divisible by $$$k$$$. This can be represented as minimum cover of the hypergraph by edges with weights = (number of vertices - 1) + (sum of elements / $$$k$$$ - 1). Is there a polynomial solution ($$$k$$$ is a parameter)?