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

В городе имеется `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