B2. Обмен книгами (сложная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие между простой и сложной версиями — ограничения.

Есть $$$n$$$ детей, каждый из которых читает уникальную книгу. В конце каждого дня $$$i$$$-й ребёнок отдаёт свою книгу $$$p_i$$$-му ребёнку (в случае, когда $$$i = p_i$$$ ребенок отдает свою книгу самому себе). Гарантируется, что все значения $$$p_i$$$ — различные целые числа от $$$1$$$ до $$$n$$$ (то есть $$$p$$$ — перестановка). Последовательность $$$p$$$ не меняется изо дня в день, она фиксированная.

Например, если $$$n=6$$$ и $$$p=[4, 6, 1, 3, 5, 2]$$$, то в конце первого дня книга $$$1$$$-го ребёнка будет у $$$4$$$-го ребёнка, книга $$$2$$$-го ребёнка будет у $$$6$$$-го ребёнка и так далее. В конце второго дня книга $$$1$$$-го ребёнка будет у $$$3$$$-го ребёнка, книга $$$2$$$-го ребёнка будет у $$$2$$$-го ребёнка и так далее.

Перед вами стоит задача — для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ определить число дней, через которое книга $$$i$$$-го ребёнка вернётся обратно к нему в первый раз.

Предположим что $$$p = [5, 1, 2, 4, 3]$$$. Книга $$$1$$$-го ребёнка будет передана следующим детям:

  • после $$$1$$$-го дня она будет у $$$5$$$-го ребёнка,
  • после $$$2$$$-го дня она будет у $$$3$$$-го ребёнка,
  • после $$$3$$$-го дня она будет у $$$2$$$-го ребёнка,
  • после $$$4$$$-го дня она будет у $$$1$$$-го ребёнка.

Таким образом, после четвертого дня книга первого ребёнка вернётся к своему владельцу. Книга четвёртого ребёнка вернётся к нему в первый раз сразу после первого дня.

Вы должны ответить на $$$q$$$ независимых запросов.

Входные данные

Первая строка входных данных содержит одно целое число $$$q$$$ ($$$1 \le q \le 1000$$$) — количество запросов. Затем следуют $$$q$$$ запросов.

Первая строка запроса содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество детей в запросе. Вторая строка запроса содержит $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$, все $$$p_i$$$ различны, т.е. $$$p$$$ является перестановкой), где $$$p_i$$$ — это ребёнок, который получит книгу от $$$i$$$-го ребёнка.

Гарантируется, что $$$\sum n \le 2 \cdot 10^5$$$ (сумма $$$n$$$ по всем запросах не превосходит $$$2 \cdot 10^5$$$).

Выходные данные

Для каждого запроса выведите ответ на него: $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$, где $$$a_i$$$ — номер дня, в конце которого книга $$$i$$$-го ребёнка вернётся к нему в первый раз в этом запросе.

Пример
Входные данные
6
5
1 2 3 4 5
3
2 3 1
6
4 6 2 1 5 3
1
1
4
3 4 1 2
5
5 1 2 4 3
Выходные данные
1 1 1 1 1 
3 3 3 
2 3 3 2 1 3 
1 
2 2 2 2 
4 4 4 1 4