题目描述

给定一个有 $N$ 条边的凸多边形。接下来要执行 $N-1$ 次移动。

一次移动选择当前多边形上相邻的两个点 $A,B$，并把点 $A$ 移动到点 $B$。这次移动的代价等于 $A,B$ 间的欧氏距离。移动后，点 $A$ 被点 $B$ 吸收，当前多边形点数减少 1。过程重复，直到多边形被压缩为一个点。

下图展示了一次把 $A$ 移动到 $B$ 的操作：

要求求出把多边形压缩为一个点的最小总代价，并在需要时输出一种达到最小总代价的移动序列。

任务

给定 $T$ 个凸多边形，根据输入中的任务编号 $p$：

1. 若 $p=1$，输出每个多边形的最小总代价；
2. 若 $p=2$，输出每个多边形的一种最优移动序列。

输入格式

第一行一个整数 $p$，表示要解决的任务编号。

第二行一个整数 $T$，表示多边形数量。

接下来依次给出 $T$ 个测试。每个测试格式如下：

第一行一个整数 $N$，表示多边形边数。

接下来 $N$ 行，每行两个整数 $x,y$，表示一个顶点坐标。顶点按逆时针顺序给出。

输出格式

根据 $p$ 的值输出：

• 若 $p=1$：对每个测试输出一行实数 ans，表示最小总代价；
• 若 $p=2$：对每个测试输出 $N-1$ 行，每行两个整数 $A,B$，表示一次移动：将顶点 $A$ 移动到顶点 $B$。

若在某次移动 A B 后顶点 $A$ 被 $B$ 吸收，那么之后再出现以 $A$ 为端点的移动均视为非法。

数据范围与限制

• $1\le T\le 5$
• $1\le N\le 2000$
• 对所有顶点，$-10^6\le x,y\le 10^6$
• 不存在两个顶点坐标完全相同
• 多边形不一定严格凸，即可以存在连续共线顶点
• 若 $p=1$，答案与标准答案误差不超过 $10^{-6}$ 即认为正确

子任务：

• 5 分：$N\le 7$
• 10 分：$N\le 15$
• 15 分：$N\le 50$
• 15 分：$N\le 100$
• 15 分：$N\le 500$
• 40 分：$N\le 2000$

对于每个测试点，解决任务 1 可获得对应分数的 80%，解决任务 2 可获得对应分数的 20%。

样例 1

输入

1
2
4
0 0
1 0
1 1
0 1
5
0 0
8 0
8 10
4 20
0 10

输出

3
36.770329614269

样例 2

输入

2
2
4
0 0
1 0
1 1
0 1
5
0 0
8 0
8 10
4 20
0 10

一种输出

3 2
4 1
2 1
4 3
5 3
3 2
2 1