Олимпиадный тренинг

Задача . B2. Обмен книгами (сложная версия)


Задача

Темы: математика поиск в глубину и подобное снм *1300

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

Есть \(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\)-го ребёнка вернётся к нему в первый раз в этом запросе.


Примеры
№Входные данныеВыходные данные
1 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

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет