건초 배선

농부 존의 소 $N$마리($4 \le N \le 12$, $N$은 짝수)가 서로 친한 소들끼리 소통하기 위한 간단한 장치를 만들었다. 친한 두 소는 건초로 감싼 전선으로 연결된다.

각 소에게는 정확히 3마리의 친구가 있으며, 소들은 한 줄로 늘어선 $N$개의 칸에 한 마리씩 들어선다. 길이가 $L$인 전선을 만드는 데에는 정확히 $L$단위의 건초가 필요하다. 예를 들어 4번 칸과 7번 칸에 있는 두 소가 친구라면, 둘을 잇는 전선에는 $3$단위의 건초가 든다.

모든 친구 쌍은 각각 별도의 전선으로 연결되어야 한다. 소들이 칸에 들어서는 순서를 가장 알맞게 정했을 때, 모든 친구 쌍을 잇는 데 필요한 건초의 최소 총량을 구하여라.

• 첫째 줄: 정수 $N$. 소는 $1$번부터 $N$번까지 번호가 매겨져 있다.
• 둘째 줄부터 $N+1$째 줄까지: $i+1$째 줄에는 $1$ 이상 $N$ 이하의 정수 3개가 공백으로 구분되어 주어지며, 이는 $i$번 소의 세 친구를 나타낸다. $i$번 소가 $j$번 소의 친구이면 $j$번 소도 $i$번 소의 친구이다.

• 첫째 줄: 모든 친구 쌍을 잇는 데 필요한 건초의 최소 총량.

소가 6마리인 경우를 생각해 보자. 1번 소는 6번, 2번, 5번 소와 친구이고 나머지도 이런 식으로 주어진다. 소를 $6, 5, 1, 4, 2, 3$의 순서로 세우면 건초가 $17$단위만 들어 최적이 된다.