P-네트워크

Pretty Networks Inc.는 입력 값들의 집합을 정해진 방식으로 변환하는 흥미로운 장치를 만드는 회사입니다. 각 변환은 이 회사가 p-네트워크라고 부르는 구조로 결정됩니다.

차수(order)가 $N$이고 크기(size)가 $M$인 p-네트워크는 $1, 2, \ldots, N$으로 번호가 매겨진 $N$개의 수평 선(wire)과 $M$개의 수직 획(stroke)으로 이루어집니다. 각 획은 서로 인접한 두 선을 연결합니다. 어떤 선 위에서도 서로 다른 두 획이 같은 지점에 닿지 않으며, 어떤 획도 선의 가장 왼쪽 끝이나 가장 오른쪽 끝에는 닿지 않습니다. 위 그림은 차수 $5$, 크기 $9$인 p-네트워크입니다.

p-네트워크가 결정하는 변환은 다음 규칙에 따라 네트워크를 따라가며 정해집니다.

1. 한 선의 가장 왼쪽 끝에서 시작하여 오른쪽으로 이동한다.
2. 획을 만날 때마다 그 획이 연결하는 선으로 옮겨 간 뒤, 계속 왼쪽에서 오른쪽으로 나아간다.
3. 어떤 선의 가장 오른쪽 끝에 도달하면 멈춘다.

선 $i$에서 출발하여 선 $j$에서 끝나면, 이 p-네트워크는 $i$를 $j$로 변환한다고 하고 $i \to j$로 씁니다. 위 그림의 p-네트워크는 다음 변환들을 실현합니다.

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

차수 $N$과 원하는 변환 집합 ${1 \to i_1,; 2 \to i_2,; \ldots,; N \to i_N}$이 주어집니다. 이 변환을 실현하는 차수 $N$의 p-네트워크가 하나라도 존재하는지 판단하고, 존재한다면 그러한 모든 p-네트워크 중 가장 작은 크기 $M$(획의 최소 개수)를 구하세요. (이 최소값은 항상 $\frac{N(N-1)}{2}$ 이하이며, 이는 회사가 다루는 상한 $4N^2$보다 훨씬 작습니다.)

입력에는 여러 개의 p-네트워크 설계 문제가 주어집니다. 각 문제는 한 줄에 값 $N, i_1, i_2, \ldots, i_N$이 하나의 공백으로 구분되어 주어집니다. $N$은 원하는 p-네트워크의 차수, 즉 선의 개수이며 ($1 \le N \le 20$), 값 $i_1, i_2, \ldots, i_N$은 p-네트워크가 변환 집합 ${1 \to i_1,; 2 \to i_2,; \ldots,; N \to i_N}$을 실현해야 함을 뜻합니다 (모든 $1 \le j \le N$에 대해 $1 \le i_j \le N$). 입력은 $N = 0$인 줄로 끝나며, 이 줄은 처리하지 않습니다.

각 설계 문제마다 한 줄을 출력합니다. 요청된 변환을 실현하는 p-네트워크가 존재하지 않으면 그 줄은 No solution이어야 합니다. 존재한다면 그 줄에는 정수 하나, 즉 그 변환을 실현하는 차수 $N$의 p-네트워크가 가질 수 있는 최소 크기 $M$(획의 최소 개수)을 출력합니다.