Plugged In

The designers of a new game console want to accept interactive input from many different sources. Using a special sensor-lined "electronic cocoon", a user could control simulated laser cannons by moving their eyebrows, accelerate or decelerate by wiggling their ears, steer in three-dimensional space by rotating their ankles, and so on -- the possibilities are endless.

The connection between the cocoon's sensors and the simulated actions is made through a special square plug with $n^2$ pins (the value of $n$ is not yet fixed). Each pin can carry the output of one sensor, though for some applications not every pin is active. The plug fits into a square socket with $n^2$ holes attached to the game inputs; again, not every hole is always used. The socket may be flipped over and rotated to produce different matchings between pins and holes. Pins and holes are each numbered consecutively in row-major order (for example, from $1$ to $n^2$ for the plug and from 1' to n²' for the socket).

Because of these rotations and flips, when $n = 4$ pin 1 can be aligned only with hole 1', 4', 13', or 16' (depending on how the plug is rotated relative to the socket). When all rotations and both the front and back of the plug are considered, pin 2 can be aligned only with hole 2', 3', 5', 8', 9', 12', 14', or 15'.

Most games need extra wiring, because a pin usually cannot be aligned directly over the hole it must connect to (for instance, connecting pin 1 to hole 11'). This wiring is done by a game-specific "wiring block" placed between the plug and the socket. The length of each wire depends on the orientation of the socket relative to the plug. Wires always run parallel to the grid lines, so the amount of wire between a pin and a hole is $1$ plus the length of a shortest grid path between them (the extra $1$ accounts for the thickness of the wiring block). Thus one unit of wire is the minimum possible, achieved when a pin sits directly over the hole it connects to.

Given a list of required connections, determine the minimum average wire length achievable over all orientations of the socket. The socket may be placed in any of its $8$ orientations: the $4$ rotations of the front face plus the $4$ rotations of the flipped back face.

For example, for the connections (1, 3'), (5, 7'), (2, 6') on a $4 \times 4$ plug and socket, the average wire length is $2.6667$ if the plug is inserted into the front of the socket without rotating it, but only $2.3333$ in the best orientation.

The input consists of several scenarios. Each scenario begins with a positive integer $n$ ($n \le 100$), the side length of the plug and socket, on a line by itself, followed by a positive integer $m$ ($m \le n^2$) on a line by itself, followed by $m$ lines. Each of these lines contains two positive integers in the range $1, \dots, n^2$: the first is a pin position in the plug and the second is a hole position in the socket. No two pairs share a common first element, and no two pairs share a common second element. The final scenario is followed by a line containing a single $0$.

For each scenario, output its number (starting from $1$) together with the smallest average wire length achievable over all rotations and flips of the socket, on a line of the form:

Scenario n: smallest average = avg

where avg is the average, rounded and displayed to exactly four decimal places. Separate the output of consecutive scenarios with a single blank line.