P5701 [CTSC1998] 站牌位置

CTSC1998 D2T2

某城市市区规划成网格状，市区由 $n+1$ 条南北走向和 $n+1$ 条东西走向的干道将其平均分为 $n^2$ 个区域， $(n+1)^2$ 个叉路口。区域及叉路口均**由上至下，由左至右**编号。 现在要在城市中划分出若干区域作为游览胜地，每一个游览胜地将会有且仅有一路公共汽车围绕它的四周运行，这路公共汽车将仅在该区域四周的四个叉路口设立四个公共汽车车站。相邻的两个区域（两个区域相邻当且仅当它们有一段公共的公路）将会共用两个公共汽车车站。 政府为每一个公共汽车车站设立一个站牌，站牌号用自然数 $1$ , $2$ ...表示且互不相同，可没想到站牌号的设置令政府大伤脑筋。原来，该城市有三个公交公司，他们有各自的规定，即： 1. 甲公司的一路公共汽车绕某一个区域运行的四个站，应该满足下面条件：从某一个站出发，**顺时针方向**经过的三个站牌牌号**单调递减**，最后回到原来的那个站。 2. 乙公司的一路公共汽车绕某一个区域运行的四个站，应该满足下面条件：从某一个站出发，**逆时针方向**经过的三个站牌牌号**单调递减**，最后回到原来的那个站。 3. 丙公司的一路公共汽车绕某个区域运行的四个站，应该满足下面条件：从某一个站出发，顺时针方向经过的三个站应是站牌号依次**先减少，再增加，再减少，最后再增加**，然后回到原来的那个站。 为公平起见，政府希望找出一个安排站牌的方法，对这 $n$ 个区域所涉及的所有的 $K$ 个站分配站牌。使三个公司能在游览胜地中开辟尽量一样多的公共汽车路线。请你编程解决上述问题。 设三个公司可开辟的公共汽车路线数分别为 $X$ , $Y$ , $Z$ , **你应使$S=(X-Y)^2+(Y-Z)^2+(Z-X)^2$最小**。

输入文件的第一行为 $n$，第二行为 $m$，表示有 $m$ 个区域为游览胜地，第三行的 $m$ 个数分别为这 $m$ 个区域的编号，相邻的两数之间用一个空格隔开。

输出文件的第一行为你所找到的 $S$ 值，第二行为 $K$ ，以下的 $K$ 行每行各有两个数，第一个数为叉路口号，第二个数为你安排该叉路口的公共汽车站牌号（站牌号应为由 $1$ 到 $K$ 的自然数，且各不相同），这 $K$ 行应按叉路口号从小到大输出。

【数据范围】 $1 \leq n \leq 7$