The designers of the new NentindoBoxStation game system want to provide interactive input from many different sources. Using a special sensor-lined "electronic cocoon" users should be able to do things such as control simulated laser cannons by moving their eyebrows, accelerate/decelerate by wiggling their ears, steer in three-dimensional space by rotating their ankles ... the possibilities are endless.
The connections between the sensors in the cocoon and the simulated actions in the computer are to be made using a special square plug with n2 pins (the value of n has not yet been determined). Each pin can carry the output from one sensor, although for some applications not all pins will be active.The plug fits into a square socket containing n2 holes that is attached to the various game inputs;again, for some games, not all input holes will be used. The socket can be flipped over and rotated to achieve different matchings between sensor pins and game inputs. Pins and socket holes are numbered consecutively in row major order (as shown below for the value n = 4).
Input will consist of a set of scenarios. Each scenario consists of a positive integer n, the side length of the plug and socket (less than or equal to 100) on a line by itself, followed by a positive integer m (less than or equal to n2) on a line by itself, followed by m lines, each containing a pair of positive integers in the range 1, . . . , n2. You may assume that no two pairs will have either a common first element or a common second element. The first integer represents a pin position in the plug, the second is a hole position in the socket. The final scenario is followed by 0 on a line by itself.
For each scenario, output the scenario number (starting with 1), followed by the smallest average distance achievable between the m pin/socket pairs after rotations and reflections are considered (assuming an appropriate routing box is used), in a line of the form:
Scenerio n: smallest average = avg
where avg is the average is rounded, and displayed, to four decimal places. Separate lines of output by a single blank line.
4 3 1 3 5 7 2 6 2 3 1 4 2 2 4 1 0
Scenario 1: smallest average = 2.3333 Scenario 2: smallest average = 1.0000