플러그 연결

새로운 게임 콘솔의 설계자들은 다양한 입력 장치로부터 상호작용 입력을 받고자 합니다. 센서가 촘촘히 박힌 특수한 "전자 코쿤(cocoon)"을 이용하면, 눈썹을 움직여 가상의 레이저 대포를 조준하고, 귀를 씰룩여 가속·감속하며, 발목을 돌려 3차원 공간에서 방향을 조종하는 등 그 가능성은 무궁무진합니다.

코쿤의 센서와 컴퓨터 속 가상 동작은 $n^2$개의 핀을 가진 정사각형 플러그로 연결됩니다($n$의 값은 아직 정해지지 않았습니다). 각 핀은 하나의 센서 출력을 전달하지만, 응용에 따라 모든 핀이 사용되지는 않습니다. 이 플러그는 게임 입력에 연결된, $n^2$개의 구멍을 가진 정사각형 소켓에 꽂힙니다. 마찬가지로 모든 구멍이 항상 사용되지는 않습니다. 소켓은 뒤집거나 회전시켜 핀과 구멍의 대응을 다르게 만들 수 있습니다. 핀과 구멍은 각각 행 우선(row-major) 순서로 연속하여 번호가 매겨집니다(예를 들어 플러그는 $1$부터 $n^2$까지, 소켓은 1'부터 n²'까지).

이러한 회전과 뒤집기 때문에, $n = 4$일 때 핀 1은 소켓을 어떻게 회전하느냐에 따라 구멍 1', 4', 13', 16' 중 하나에만 정렬될 수 있습니다. 회전과 플러그의 앞면·뒷면을 모두 고려하면, 핀 2는 구멍 2', 3', 5', 8', 9', 12', 14', 15' 중 하나에만 정렬될 수 있습니다.

대부분의 게임은 추가 배선이 필요합니다. 핀을 연결해야 할 구멍 바로 위에 정렬할 수 없는 경우가 많기 때문입니다(예: 핀 1을 구멍 11'에 연결). 이 배선은 플러그와 소켓 사이에 놓이는 게임 전용 "배선 블록"으로 이루어집니다. 각 전선의 길이는 플러그에 대한 소켓의 방향에 따라 달라집니다. 전선은 항상 격자선과 평행하게 지나가므로, 한 핀과 한 구멍 사이의 전선 길이는 두 지점 사이 최단 격자 경로의 길이에 $1$을 더한 값입니다(더해지는 $1$은 배선 블록 자체의 두께 때문입니다). 따라서 핀이 연결할 구멍 바로 위에 놓일 때 전선은 최소인 $1$이 됩니다.

연결해야 할 목록이 주어질 때, 소켓의 모든 방향에 대해 달성 가능한 최소 평균 전선 길이를 구하세요. 소켓은 8가지 방향으로 놓을 수 있습니다: 앞면의 4가지 회전과, 뒤집은 뒷면의 4가지 회전입니다.

예를 들어 $4 \times 4$ 플러그와 소켓에서 연결 (1, 3'), (5, 7'), (2, 6')의 평균 전선 길이는, 소켓을 회전하지 않고 앞면에 그대로 꽂으면 $2.6667$이지만, 가장 좋은 방향으로 놓으면 $2.3333$입니다.

입력은 여러 개의 시나리오로 구성됩니다. 각 시나리오는 플러그와 소켓 한 변의 길이인 양의 정수 $n$($n \le 100$)이 한 줄에 주어지고, 이어서 양의 정수 $m$($m \le n^2$)이 한 줄에 주어지며, 그다음 $m$개의 줄이 이어집니다. 각 줄에는 $1, \dots, n^2$ 범위의 두 양의 정수가 있으며, 첫 번째는 플러그의 핀 위치, 두 번째는 소켓의 구멍 위치입니다. 어떤 두 쌍도 첫 번째 원소가 같지 않고, 어떤 두 쌍도 두 번째 원소가 같지 않습니다. 마지막 시나리오 다음에는 $0$ 하나만 있는 줄이 옵니다.

각 시나리오에 대해, 시나리오 번호($1$부터 시작)와 소켓의 모든 회전·뒤집기에 대해 달성 가능한 최소 평균 전선 길이를 다음 형식의 한 줄로 출력하세요.

Scenario n: smallest average = avg

여기서 avg는 소수점 아래 넷째 자리까지 반올림하여 표시한 평균입니다. 연속한 두 시나리오의 출력은 빈 줄 하나로 구분합니다.