G2. Средняя демоническая задача (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Ключевое отличие между двумя версиями выделено жирным шрифтом.

Группа из $$$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
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]$$$. Поскольку этот массив такой же, как в предыдущем году, этот год является стабильным.