重要说明： 本题不是提交 C++ / Python 程序的普通题。你需要下载公开输入数据，针对每个输入文件构造对应的输出文件，然后将所有输出文件打包成一个 .zip 文件提交。

---

公开输入数据下载

请先下载本题的公开输入数据包：

下发文件

数据包中包含：

input1.in
input2.in
input3.in
input4.in
input5.in
input6.in
input7.in
input8.in
input9.in
input10.in
README_提交说明.txt

你需要分别根据 input1.in 到 input10.in 构造对应的输出文件 input1.out 到 input10.out。

---

题目描述

农夫 Juhan 在牧场中打下了 $N$ 根柱子。牧场可以看作一个坐标平面，每根柱子都有整数坐标。

Juhan 想在柱子之间拉上铁丝，使得铁丝之间互不相交。也就是说，铁丝段之间只能在公共端点处相接，不能在内部相交。

这些铁丝需要形成若干个三角形围栏，用来安置羊。羊很任性，因此每只羊都必须单独待在一个围栏中。

由于农业目前景气不好，Juhan 希望在能够容纳最大可能数量羊的前提下，使用尽可能少的铁丝。Juhan 拥有的铁丝总量有限，不能使用超过这个长度的铁丝。

请你为每个给定输入文件构造一个对应的输出文件。

---

输入格式

每个输入文件格式如下。

第一行包含两个整数 $N$ 和 $M$，分别表示柱子数量和 Juhan 拥有的铁丝总长度。

接下来 $N$ 行，每行包含两个整数 $X_i,Y_i$，表示第 $i$ 根柱子的坐标。

柱子按照输入顺序编号为 $1,2,\ldots,N$。

---

输出格式

每个输出文件格式如下。

第一行输出两个数 $K$ 和 $L$，分别表示铁丝段数量和使用的铁丝总长度。

接下来 $K$ 行，每行输出两个整数 $A$ 和 $B$，表示在柱子 $A$ 与柱子 $B$ 之间拉一段铁丝。

其中：

• $1 \le A,B \le N$；
• $A \ne B$；
• $L$ 应输出到小数点后恰好 $6$ 位；
• 输出的 $L$ 应与所有铁丝段的实际欧几里得长度之和一致；
• 铁丝总长度不能超过输入中的 $M$；
• 任意两条铁丝段不能在内部相交；
• 形成的三角形围栏数量应尽可能多，并在此前提下尽量减少铁丝总长度。

---

数据范围

对于所有公开输入数据：

$$3 \le N \le 10000$$ $$1 \le M \le 10^{10}$$ $$-10^5 \le X_i,Y_i \le 10^5$$

保证每个测试点中都存在至少一种合法方案，使得使用的铁丝总长度不超过 $M$。

---

提交方式

本题为 多文件提交答案题。

你不需要提交源代码。你需要提交一个 .zip 压缩包，压缩包根目录下必须直接包含以下 10 个输出文件：

input1.out
input2.out
input3.out
input4.out
input5.out
input6.out
input7.out
input8.out
input9.out
input10.out

请注意：

• 压缩包中不要包含源代码；
• 压缩包中不要包含输入文件；
• 压缩包中不要再套一层文件夹；
• 文件名必须严格为 input1.out 到 input10.out；
• 每个 .out 文件分别对应同编号的 .in 文件。

正确的压缩包结构示例：

submit.zip
├── input1.out
├── input2.out
├── input3.out
├── input4.out
├── input5.out
├── input6.out
├── input7.out
├── input8.out
├── input9.out
└── input10.out

错误示例：

submit.zip
└── kari_answer
    ├── input1.out
    ├── input2.out
    └── ...

这种写法多套了一层文件夹，评测系统可能无法读取对应输出文件。

---

评分方式

每个测试点满分 10 分，总分 100 分。

原题是输出优化题。对于每个测试点，一个合法输出会根据使用的铁丝总长度进行评分。设：

• $M$ 为输入文件中给出的铁丝总长度上限；
• $C$ 为当前提交方案实际使用的铁丝总长度；
• $U$ 为该测试点的参考最优长度。

则该测试点的得分比例为：

$$\frac{M-C}{M-U}$$

该比例最高按 $1$ 计算。因此，如果你的方案不劣于参考方案，则该测试点可以获得满分 10 分。

如果输出不满足题目条件，例如：

• 输出格式错误；
• 第一行的 $K$ 或 $L$ 不合法；
• 柱子编号越界；
• 存在重复铁丝段；
• 铁丝段在内部相交；
• 使用铁丝总长度超过 $M$；
• 输出的 $L$ 与实际长度不一致；
• 形成的三角形围栏数量不是最大可能值；

则该测试点得 0 分。

---

样例

样例输入

4 19
0 0
0 3
3 0
4 3

样例输出

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

样例解释

在这个样例中，四根柱子位于一个梯形的四个顶点，Juhan 有 $19$ 单位长度的铁丝。

一种方案是布置梯形的四条边和较短的一条对角线，从而形成两个三角形围栏。样例输出使用的铁丝总长度为 $17.404918$。

另一种合法方案是布置梯形的四条边和较长的一条对角线，此时铁丝消耗为 $18.162278$。如果两种方案都被提交，那么提交较长对角线方案的得分约为：

$$10 \cdot \frac{19-18.162278}{19-17.404918} \approx 5.25$$

---

提示

本题是提交答案题。你可以使用任意方式生成输出文件，例如手工构造、编写本地程序求解、使用几何算法或启发式优化方法。

只要最终提交的 .zip 中包含符合要求的 10 个 .out 文件即可。