题目描述

这是问题的简化版。两个版本之间的关键区别以粗体显著标出。

有一群 $n$ 只蜘蛛聚在一起交换他们的毛绒玩具。最初，每只蜘蛛都有 $1$ 个毛绒玩具。每年，如果第 $i$ 只蜘蛛拥有至少一个毛绒玩具，它就会给第 $r_i$ 只蜘蛛一个毛绒玩具。否则，它将不会进行任何操作。注意，所有的毛绒玩具转移是同时进行的。在这个版本中，如果一只蜘蛛在任意时刻拥有超过 $1$ 个毛绒玩具，它们会丢掉多余的，只保留一个。

如果在某年开始时，每只蜘蛛拥有的毛绒玩具数量与上一年相同，则这一年的过程是稳定的。请注意，第 $1$ 年永远不会是稳定的。

请找出该过程中首次出现稳定的年份。

输入格式

第一行输入一个整数 $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$。

输出格式

对于每一个测试用例，请在新的一行输出一个整数，表示过程首次达到稳定的年份。

样例

5
2
2 1
5
2 3 4 5 1
5
2 1 4 2 3
5
4 1 1 5 4
10
4 3 9 1 6 7 9 10 10 3

2
2
5
4
5

样例说明

对于第二个测试用例：

• 在第 $1$ 年，每只蜘蛛的毛绒玩具数量为 $[1, 1, 1, 1, 1]$。然后进行当年的交换。
• 到了第 $2$ 年，各蜘蛛的毛绒玩具数量仍然为 $[1, 1, 1, 1, 1]$。由于数量没有变化，因此这一年是稳定的。

对于第三个测试用例：

• 在第 $1$ 年，所有蜘蛛的毛绒玩具数量为 $[1, 1, 1, 1, 1]$。然后进行第 $1$ 年的交换。
• 在第 $2$ 年，这些数量变为 $[1, 1, 1, 1, 0]$ 。然后进行第 $2$ 年的交换。即便有两只蜘蛛给了第 $2$ 只蜘蛛毛绒玩具，第 $2$ 只蜘蛛也只能保留一个。
• 到第 $3$ 年，数量变为 $[1, 1, 0, 1, 0]$。然后进行交换。
• 第 $4$ 年，数量变为 $[1, 1, 0, 0, 0]$。然后进行交换。
• 第 $5$ 年，数量仍然为 $[1, 1, 0, 0, 0]$。由于数量保持不变，这一年是稳定的。

本翻译由 AI 自动生成

来源

Codeforces 2044G1，英文题名 Medium Demon Problem (easy version)。