Наилучшие друзья
Наилучшие друзья
Вы - учитель в новом детском саду "Маленькие кодеры". В Вашем классе имеется n детей, у каждого из них имеется уникальный идентификационный номер ученика (от 1 до n). Каждый ребенок в классе имеет единственного лучшего друга, и Вы знаете этого лучшего друга для каждого ребенка. Отношение дружбы не всегда взаимно, то есть если B лучший друг А, то это не значит что A лучший друг B.
Ваш завтрашний план урока включает в себя мероприятие, в котором участники должны сидеть в кругу. Вы хотите сделать мероприятие настолько успешным, насколько это возможно, создав максимально возможный круг детей, чтобы каждый ребенок в круге сидел прямо рядом со своим наилучшим другом либо слева, либо справа. Любые дети, не входящие в круг, будут наблюдать за мероприятием, не участвуя в нем.
Какое наибольшее количество детей может быть в кругу?
Входные данные
Первая строка содержит количество тестов t (1 ≤ t ≤ 100). Далее следуют t тестов. Каждый тест состоит из двух строк. Первая строка содержит число n (3 ≤ n ≤ 1000) - общее количество детей в классе. Вторая строка содержит n целых чисел F1
, F2
, ..., Fn
, где Fi
(1 ≤ Fi
≤ n) - ID номер школьника, являющегося наилучшим другом школьника с ID номером i.
Выходные данные
Для каждого теста выведите одну строку "Case #x: y", где x - номер теста (начиная с 1) и y - наибольшее количество детей, которое можно расположить по кругу так чтобы каждый ребенок в кругу располагался возле своего наилучшего друга.
4 4 2 3 4 1 4 3 3 4 1 4 3 3 4 3 10 7 8 10 10 9 2 9 6 3 3
Case #1: 4 Case #2: 3 Case #3: 3 Case #4: 6