CF2044G2.Medium Demon Problem (hard version)

这是该问题的困难版本。两个版本之间的关键区别已用粗体强调。

有一群 $n$ 只蜘蛛聚在一起交换毛绒玩具。一开始，每只蜘蛛手里都有一个毛绒玩具。每年，如果第 $i$ 只蜘蛛至少有一个毛绒玩具，它会把自己的一个毛绒玩具送给第 $r_i$ 只蜘蛛。否则，它会选择不做任何事情。注意，所有毛绒玩具的转移同时进行。在这个版本中，每只蜘蛛在任何时候都可以拥有多个毛绒玩具。

如果今年（在进行交换之前）每只蜘蛛拥有的毛绒玩具数量与去年（交换之前）相同，那么这一年就是稳定的。需要注意的是，第一年不可能是稳定的。

请找出施行直到稳定的第一个年份。

第一行输入一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 2 \cdot 10^5$），表示蜘蛛的数量。

接下来的一行包含 $n$ 个整数 $r_1, r_2, \ldots, r_n$（$1 \leq r_i \leq n, r_i \neq i$），表示每只蜘蛛所指定的收件蜘蛛编号。

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

对于每个测试用例，输出一个整数代表过程第一次变得稳定的年份。

对于第二个测试用例：

• 第一年，每只蜘蛛拥有的毛绒玩具数量为：$[1, 1, 1, 1, 1]$。接下来进行第一次交换。
• 第二年，每只蜘蛛拥有的毛绒玩具数量仍为：$[1, 1, 1, 1, 1]$。由于这个数组与去年相同，所以第二年是稳定的。

对于第三个测试用例：

• 第一年，每只蜘蛛拥有的毛绒玩具数量为：$[1, 1, 1, 1, 1]$。接下来进行第一次交换。
• 第二年，每只蜘蛛拥有的毛绒玩具数量变为：$[1, 2, 1, 1, 0]$。随后进行第二次交换。
• 第三年，每只蜘蛛拥有的毛绒玩具数量变为：$[1, 3, 0, 1, 0]$。随后进行第三次交换。
• 第四年，每只蜘蛛拥有的毛绒玩具数量变为：$[1, 4, 0, 0, 0]$。随后进行第四次交换。
• 第五年，每只蜘蛛拥有的毛绒玩具数量仍为：$[1, 4, 0, 0, 0]$。由于这个阵列与上一年相同，第五年是稳定的。

本翻译由 AI 自动生成