Minimum Hay Bale Connection Cost

Farmer John has N cows (where \(4 \le N \le 12\) and \(N\) is even). Each cow has exactly 3 friends. To enable communication between every pair of friends, a separate cable must be built. The cows are to be arranged in a single row of hay bales. A cable connecting two cows placed at positions \(p\) and \(q\) (with \(p\) and \(q\) being the indices of their hay bales in the row) requires exactly \(|p - q|\) hay bales to protect it.

For example, if one cow is placed at hay bale 4 and her friend is placed at hay bale 7, then protecting the cable connecting them requires \(\lvert 7-4\rvert = 3\) hay bales.

Every friendship pair must have its own dedicated cable. Since you are free to arrange the cows in any order, determine the minimum number of hay bales required to protect all the cables.

Note: The input graph is guaranteed to be 3-regular (each cow has exactly 3 friends), so there will be exactly \(\frac{3N}{2}\) friendship pairs.

inputFormat

The first line contains an integer \(N\) (\(4 \le N \le 12\) and \(N\) is even), the number of cows.

Each of the next \(\frac{3N}{2}\) lines contains two integers \(u\) and \(v\) (1-indexed) indicating that cow \(u\) and cow \(v\) are friends.

outputFormat

Output a single integer, the minimum total number of hay bales needed to protect all the cables.

sample

4
1 2
1 3
1 4
2 3
2 4
3 4

10