E. 计算几何

题目描述

你有一个正 $2n$ 边形，点的标号顺时针为 $0,1,2,\cdots,2n-1$，最开始在 $i,(i+1)\bmod 2n$ 之间都有一条双向边。你需要添加 $2n-3$ 条不能在非端点处相交的双向边。同时，你需要满足最后没有重边。

每个点都有一个类型，在 $0\sim n-1$ 之间。而对于每种类型 $i$，保证恰好有两个点的类型为 $i$，记为 $a_i,b_i$。你需要最小化 $\sum_{i=0}^{n-1} \text{dist}(a_i,b_i)$。其中 $\text{dist}(u,v)$ 表示 $u\to v$ 最少经过的边数。

输入格式

本题含有多组测试数据。

第一行一个整数 $T$ 表示数据组数。对于每组数据：

• 第一行一个整数 $n$。
• 接下来 $n$ 行，每行两个整数表示 $a_i,b_i$。

输出格式

对于每组测试数据，输出 $2n-2$ 行。

• 前 $2n-3$ 行中每行两个正整数 $x,y$ 表示你构造的方案中的一条边 $(x,y)$。
• 最后一行一个正整数表示 $\sum_{i=0}^{n-1} \text{dist}(a_i,b_i)$ 的最小值。

样例 #1

样例输入 #1

3
4
5 3
2 1
4 0
6 7
6
1 5
11 10
2 4
7 0
6 8
3 9
9
16 9
14 6
10 1
15 7
0 13
2 11
12 8
4 3
5 17

样例输出 #1

5
10
16

样例解释 #1

这里仅显示了最小值。

显示具体构造会对此题 AC 率造成巨大影响，故不予展示。

数据范围

如果你回答对了第一问，可以获得 $70\%$ 的分数，但是你必须遵守输出格式，否则会得到 $0$ 分的高分。

对于所有测试数据，$2\leq n\leq 2\times 10^5,\sum n\leq 2\times 10^5$。

子任务 $6$ 的时间限制为 $3$ 秒。