← 返回题目列表

Codeforces · 2044/G2

G2. 中等恶魔问题(困难版)

中文机器翻译题面 查看原题

这是问题的困难版本。两个版本之间的主要区别以粗体突出显示。

一群 $$$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$$$。

输出

对于每个测试用例,在新行中输出一个整数,即过程变得稳定的第一年。

示例

输入 #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
5
5

注意

对于第二个测试用例:

- 在 $$$1$$$ 年,以下数组显示每个蜘蛛拥有的毛绒玩具数量:$$$[1, 1, 1, 1, 1]$$$。然后,一年 $$$1$$$ 的交换发生了。
- 在 $$$2$$$ 年,以下数组显示每个蜘蛛拥有的毛绒玩具数量:$$$[1, 1, 1, 1, 1]$$$。由于这个阵法和往年一样,所以今年是稳定的。

对于第三个测试用例:

- 在 $$$1$$$ 年,以下数组显示每个蜘蛛拥有的毛绒玩具数量:$$$[1, 1, 1, 1, 1]$$$。然后,一年 $$$1$$$ 的交换发生了。
- 在 $$$2$$$ 年,以下数组显示每个蜘蛛拥有的毛绒玩具数量:$$$[1, 2, 1, 1, 0]$$$。然后,年 $$$2$$$ 的交换发生了。
- 在 $$$3$$$ 年,以下数组显示每个蜘蛛拥有的毛绒玩具数量:$$$[1, 3, 0, 1, 0]$$$。然后,年 $$$3$$$ 的交换发生了。
- 在 $$$4$$$ 年,以下数组显示每个蜘蛛拥有的毛绒玩具数量:$$$[1, 4, 0, 0, 0]$$$。然后,年 $$$4$$$ 的交换发生了。
- 在 $$$5$$$ 年,以下数组显示每个蜘蛛拥有的毛绒玩具数量:$$$[1, 4, 0, 0, 0]$$$。由于这个阵法和往年一样,所以今年是稳定的。