P-Networks

Pretty Networks Inc. builds curious artifacts that transform a set of input values in a prescribed way. Each transformation is determined by what they call a p-network.

A p-network of order $N$ and size $M$ has $N$ horizontal wires numbered $1, 2, \ldots, N$ and $M$ vertical strokes. Each stroke connects two consecutive wires. No two strokes touch the same point of any wire, and no stroke touches the leftmost or rightmost point of any wire. The picture above shows a p-network of order $5$ and size $9$.

The transformation determined by a p-network follows from these traversal rules:

1. start at the leftmost point of one wire and move to the right;
2. whenever a stroke appears, move to the wire it connects and keep going from left to right;
3. stop when the rightmost point of a wire is reached.

If starting on wire $i$ the traversal ends on wire $j$, we say the p-network transforms $i$ into $j$, written $i \to j$. The p-network in the picture realizes the transformations

$\{1 \to 3,\; 2 \to 5,\; 3 \to 4,\; 4 \to 1,\; 5 \to 2\}.$

You are given an order $N$ and a desired set of transformations $\{1 \to i_1,\; 2 \to i_2,\; \ldots,\; N \to i_N\}$. Decide whether any p-network of order $N$ can realize them. When one exists, report the minimum possible size $M$, i.e., the smallest number of strokes over all p-networks that realize the transformations. (Such a minimum never exceeds $\frac{N(N-1)}{2}$, which is well below the $4N^2$ bound the company works with.)

The input contains several p-network design problems. Each problem is a single line with the values $N, i_1, i_2, \ldots, i_N$ separated by single spaces. Here $N$ is the order of the desired p-network, i.e., its number of wires ($1 \le N \le 20$), and the values $i_1, i_2, \ldots, i_N$ mean the p-network must realize the transformations $\{1 \to i_1,\; 2 \to i_2,\; \ldots,\; N \to i_N\}$ ($1 \le i_j \le N$ for every $1 \le j \le N$). The input ends with a line containing $N = 0$, which must not be processed.

For each design problem output a single line. If no p-network realizes the requested transformations, the line must be No solution. Otherwise the line must contain a single integer: the minimum size $M$ (number of strokes) of a p-network of order $N$ that realizes them.