Description

Farmer John has $N$ cows ($4 \leq N \leq 12$, and $N$ is even). They set up a homemade system that allows cows and their friends to communicate through lines protected by hay bales.

Each cow in the pasture has exactly $3$ friends, and the cows must be arranged in a single row of hay bales.

A line of length $L$ occupies exactly $L$ hay bales to protect it. For example, if two cows are placed at hay bales $4$ and $7$ and they are friends, then we need $3$ hay bales to build the line that connects them.

Assume that every pair of friends must be connected by a separate line, and we may rearrange the cows arbitrarily. Compute the minimum total number of hay bales required to build all the lines.

Input Format

Line $1$: An integer $N$. For convenience, the cows are numbered $1 \sim N$.

Lines $2, 3, \dots, N + 1$: Each line contains three integers in $1 \sim N$. The numbers on line $i + 1$ are the indices of cow $i$’s three friends. Obviously, if cow $i$ is one of cow $j$’s three friends, then cow $j$ is also one of cow $i$’s three friends.

Output Format

A single integer representing the minimum number of hay bales required to build the lines.

6
6 2 5
1 3 4
4 2 6
5 3 2
4 6 1
1 5 3

17

Hint

Sample explanation: the best arrangement of the cows is $\{6, 5, 1, 4, 2, 3\}$, in which case we need only $17$ hay bales.

Translated by ChatGPT 5