修公路（road）
时间限制：2s。 空间限制：1024MB。
题目描述
有 $2n$ 座城市，编号为 $0,1,\dots, 2n-1$。这 $2n$ 座城市在平面上的位置按照 $0,1,\dots, 2n-1$ 的顺序顺时针构成了一个正 $2n$ 边形。
公路是连接两个城市之间的一条直的线段。公路是双向的。汽车可以花费 $1$ 的时间通过一条公路从该公路连接的一座城市到达另一座城市。
一开始，相邻的两座城市之间有一条公路，即第 $i$ 座城市和第 $(i+1)\bmod 2n$ 座城市之间有一条公路（$0\le i\le 2n-1$）。
为了方便交通，需要另外新修恰好 $2n-3$ 条公路。
公路需要满足以下条件：
- 每条公路连接着两座不同的城市。
- 对任意两座城市，最多只能有一条公路连接着它们（包括原有的公路）。
- 对任意两条公路，它们不能在非端点处相交。
每座城市有一个 $0,1,\dots,n-1$ 之间的数值代表该城市的类型。对每种类型 $i$（$0\le i\le n-1$）都有恰好 $2$ 座城市的类型为 $i$，记这两座城市为 $a_i$ 和 $b_i$。
现在你需要决定修公路的方案，使得 $\sum\limits_{i=0}^{n-1} \operatorname{dist}(a_i,b_i)$ 最小。其中 $\operatorname{dist}(a_i,b_i)$ 表示从城市 $a_i$ 到达城市 $b_i$ 最少需要花费的时间。
输入格式
本题含有多组数据。第一行一个整数 $t$ 表示数据组数。对于每组数据：
第一行一个整数 $n$。
接下来 $n$ 行，每行两个整数表示 $a_i,b_i$。
输出格式
对于每组数据：
首先输出 $2n-3$ 行，每行两个 $[0,2n-1]$ 之间的整数，表示你修建的公路所连接两个城市的编号。
接下来一行输出一个整数表示最小的 $\sum\limits_{i=0}^{n-1} \operatorname{dist}(a_i,b_i)$。
样例
样例 $1$
样例输入
1
4
3 6
5 1
0 7
2 4样例输出
6 2
6 0
2 4
2 5
6 1
6数据范围
对于所有数据，有 $t\ge 1$，$n\ge 2$，$\sum n\le 2\times 10^5$。
- Subtask 1 (10 points)：$t\le 10, n\le 5$。
- Subtask 2 (10 points)：$t\le 10, n\le 10$。
- Subtask 3 (10 points)：$a_i=i,b_i=i+n$。
- Subtask 4 (14 points)：$\sum n\le 100$。
- Subtask 5 (14 points)：$\sum n\le 1000$。
- Subtask 6 (42 points)：无特殊限制。
若 $\sum\limits_{i=0}^{n-1}\operatorname{dist}(a_i,b_i)$ 的最小值计算正确，且输出格式符合要求，则可获得 $50\%$ 的分数。