printРабочее место участника

printЗадачи

1919. Покраска дорог

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В городе имеется `N` перекрестков и `N` дорог с односторонним движением, соединяющих эти перекрестки. Известно, что на каждый перекресток можно приехать ровно по одной дороге.
Акимат города решил выкрасить дороги в различные цвета таким образом, чтобы в одном перекрестке не соединялись дороги одинакового цвета и количество использованных цветов было минимальным. Акимы других городов решили не отставать и также захотели перекрасить у себя дороги.
Помогите им определить, какое минимальное количество различных цветов понадобится для каждого города.
Первая строка входного файла содержит целое число `K` (`1\ ≤\ K\ ≤\ 10`) — количество городов. Далее идет описание `K` городов. Первая строка каждого описания содержит одно целое число: `N` (`2\ ≤\ N\ ≤\ 100000`) — количество перекрестков в городе. Следующая строка содержит `N` чисел, разделенных пробелом — описание дорог. Если `i`-е число в этой строке равно `X_i`, это значит, что есть дорога, по которой можно проехать от `X_i`-го перекрестка к `i`-ому (`1\ ≤\ X_i\ ≤\ N`, `X_i\ ≠\ i`).
В выходной файл для каждого города выведите `K` строк, содержащих по одному целому числу, — минимальное количество различных цветов, необходимых для выполнения задачи в каждом городе.

Пример ввода

2
4
4 1 2 3
5
4 1 2 3 4

Пример вывода

2
3

25931.png


Источник: 3-й этап Республиканской олимпиады по информатике 2013, Казахстан
loading