Строительство метро в Бергороде подходит к концу! Президент Берляндии решил посетить этот город и взглянуть на новое метро своими глазами.
Метро состоит из n станций. Оно построено по всем правилам Бергородского Транспортного Закона:
- Для каждой станции i существует ровно один поезд, идущий от этой станции. Его конечная станция — pi, возможно, что pi = i;
- Для каждой станции i существует ровно одна станция j такая, что pj = i.
Президент рассмотрит выгодность метро после посещения. Выгодность — это количество таких упорядоченных пар (x, y), что посетитель начнет на станции x, а после, воспользовавшись несколькими поездами (возможно нулевым количеством), прибудет на станцию y (1 ≤ x, y ≤ n).
Мэр Бергорода считает, что если выгодность метро недостаточно высока, то Президент может заменить мэра в городе (разумеется, текущий мэр не хочет, чтобы это произошло). Перед посещением Президентом города мэр успеет перестроить некоторые части метро, таким образом, изменяя значения pi для не более чем двух станций метро. Конечно, нарушать Бергородский Транспортный Закон недопустимо, поэтому метро должно подчиняться Закону и после изменений.
Мэр хочет перестроить такие части метро, чтобы выгодность метро стала максимальной возможной. Помогите ему посчитать, какую максимальную выгодность он может получить.
Примечание
В первом примере мэр может поменять p2 на 3 и p3 на 1, тогда будет 9 пар: (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3).
Во втором примере можно поменять p2 на 4 и p3 на 5.