CF1411F The Thorny Path

据传说，河内寺庙中保存着一个由 $1$ 到 $n$ 的整数排列。寺庙前排成一行的 $n$ 块颜色各异的石头。僧侣们可以对石头进行如下操作：选择一个位置 $i$（$1 \le i \le n$），然后对位置 $i$、$p[i]$、$p[p[i]]$、…… 上的石头进行循环移动。即，原本在位置 $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$。

对于每个测试用例，输出一行两个整数：世界最多能持续的天数（对 $10^9+7$ 取模），以及所需的最少交换次数。

我们用字母给石头的颜色编号。以下是第一个样例前两个测试用例的解释： 1. 使用排列 $[2, 3, 1]$，从 ABC 可以得到 CAB 和 BCA。这已经是最大可能的结果。 2. 使用排列 $[2, 1, 3]$，只能从 ABC 得到 BAC。如前例所示，对于 $n=3$，两种排列不是最大可能的不同排列数。为了得到最优排列，例如可以交换 $1$ 和 $3$，得到排列 $[2, 3, 1]$。 由 ChatGPT 4.1 翻译