描述

新型NentindoBoxStation游戏系统的设计者希望从多种不同的传感器来源获取交互式输入。通过使用一种特殊的带有传感器的"电子茧"，用户能够通过多种动作控制游戏，例如：通过眉毛移动控制模拟激光炮、通过耳朵摆动加速/减速、通过脚踝旋转在三维空间中导航等等，可能性无穷无尽。

传感器与游戏输入之间的连接将通过一种特殊的方形插头实现，该插头具有n²个引脚（n的具体值尚未确定）。每个引脚可以传输一个传感器的输出，尽管某些应用可能不会使用所有引脚。插头插入一个同样具有n²个孔的方形插座中，该插座连接到各种游戏输入；同样，某些游戏可能不会使用所有输入孔。插座可以翻转和旋转，以实现传感器引脚和游戏输入孔之间的不同匹配方式。引脚和插座孔的编号按行主序连续排列（如下图所示，n=4的例子）。


显然，引脚1只能连接到孔1'、4'、13'或16'（具体取决于插头相对于插座的旋转方式）。如果考虑所有旋转和插头正反面的连接方式，引脚2可以连接到孔2'、3'、5'、8'、9'、12'、14'或15'。

大多数游戏需要额外的布线来实现连接，因为无法直接将引脚与对应的插座孔匹配（例如，将引脚1连接到图中的孔11'）。这种布线将通过一种特殊的、针对特定游戏的"布线块"实现，该布线块将放置在插头和插座之间。这些电线的长度取决于插座相对于插头的方向。给定一组必须建立的连接列表，你需要帮助设计者确定布线块中连接所需的最小平均线长。电线始终与网格线平行，因此插头引脚和插座孔之间的电线长度为1加上节点之间的最短网格路径长度（额外的"1"是由于布线块本身的厚度）。因此，最小需要1单位长度的电线（当引脚直接位于要连接的孔上方时）。

例如，对于上图中的插头和插座，给定连接集合(1,3')、(5,7')、(2,6')，如果不旋转插座并将插头正面插入插座，这些连接对的平均距离为2.6667；但如果将插座旋转180度并水平翻转，将插头反面插入插座，平均距离仅为2.3333。

输入

输入由多个测试场景组成。每个场景包含：

• 一个正整数n（单独一行），表示插头和插座的边长（n ≤ 100）
• 一个正整数m（单独一行），表示连接对的数量（m ≤ n²）
• 接下来的m行，每行包含两个正整数，范围在1到n²之间。可以假设没有两对连接具有相同的第一个元素或相同的第二个元素。第一个整数表示插头中的引脚位置，第二个表示插座中的孔位置。

最后一个场景后跟着一行单独的0。

输出

对于每个场景，输出场景编号（从1开始），以及考虑所有旋转和反射后，m个引脚/插座连接对可实现的最小平均距离，格式如下：

Scenario n: smallest average = avg

其中avg是四舍五入到四位小数的平均值。每个场景的输出之间用一个空行分隔。

示例输入1

4
3
1 3
5 7
2 6
2
3
1 4
2 2
4 1
0

示例输出1

Scenario 1: smallest average = 2.3333

Scenario 2: smallest average = 1.0000

来源

2002年北美东部中部地区竞赛