这是问题的简单版本。两个版本之间的主要区别以粗体突出显示。
一群 $$$n$$$ 蜘蛛聚集在一起交换毛绒玩具。最初,每只蜘蛛都有 $$$1$$$ 毛绒玩具。每年,如果蜘蛛 $$$i$$$ 至少有一个毛绒玩具,他就会恰好给蜘蛛 $$$r_i$$$ 一个毛绒玩具。否则,他什么也不会做。请注意,所有毛绒玩具转移都是同时发生的。在此版本中,如果任何蜘蛛在任何时间点拥有超过 $$$1$$$ 毛绒玩具,它们都会扔掉除 $$$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$$$。
输出
对于每个测试用例,在新行中输出一个整数,即过程变得稳定的第一年。
示例
输入 #1
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
输出 #1
2 2 5 4 5
注意
对于第二个测试用例:
- 在 $$$1$$$ 年,以下数组显示每个蜘蛛拥有的毛绒玩具数量:$$$[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]$$$。然后,年 $$$3$$$ 的交换发生了。
- 在 $$$4$$$ 年,以下数组显示每个蜘蛛拥有的毛绒玩具数量:$$$[1, 1, 0, 0, 0]$$$。然后,年 $$$4$$$ 的交换发生了。
- 在 $$$5$$$ 年,以下数组显示每个蜘蛛拥有的毛绒玩具数量:$$$[1, 1, 0, 0, 0]$$$。由于这个阵法和往年一样,所以今年是稳定的。