N коров (4 <= N <= 12, N четное), построили примитивную систему для проводной коммуникации пар дружественных коров
Каждая корова имеет ровно 3 друзей в амбаре и коровы должны занять один ряд в амбаре из N стойл. Провод длины L требуется, чтобы соединить друзей в стойлах на расстоянии L. Например, если друзья находятся в стойлах 4 и 7, то требуется провод длины 3, чтобы их соединить.
Каждая пара коров должна быть соединена отдельным проводом. Определите минимальную длину провода, требуемую для организации такой сети наилучшим образом.
PROBLEM NAME: haywire
Формат входных данных
* Строка 1: Цело число N. Коровы пронумерованы 1..N.
* Строки 2..1+N: Каждая строка содержит три разделенных пробелом целых числа в диапазоне от 1 до N. Строка i+1 содержит числовые идентификаторы трех друзей коровы i. Если корова i дружит с коровой j, то и корова j дружит с коровой i.
Формат выходных данных
* Строка 1: Минимальная суммарная длина провода, чтобы соединить все пары дружественных коров.
Примечание
Лучшее упорядочивание коров есть 6, 5, 1, 4, 2, 3, и оно требует только 17 единиц длины провода.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
6 2 5
1 3 4
4 2 6
5 3 2
4 6 1
1 5 3
|
17
|