题目描述
在糕棠国，苔山皇帝胖虎正为了《大学物理》的期末考试焦头烂额。为了高效备考，他决定更欣一份基于"线段树"的复习大纲。
遗憾的是，在划分复习区间时，他记错了物理公式的边界条件。于是，这份复习大纲不再从中间平分知识点，而是每个大章节都可能被随机划分成任意的两部分。
尽管如此，这依然是一棵合法的二叉线段树结构：
- 根节点表示全部知识点的总区间 $[1, n]$；
- 每个叶子节点表示某个单一知识点的区间 $[i, i]$；
- 每个非叶子节点表示一个包含多个连续知识点的区间 $[l, r]$，并被划分成两个子区间 $[l, x]$ 和 $[x + 1, r]$，其中 $l \leq x < r$。
现在，给你这棵"复习大纲树"上所有节点对应的区间。请注意，输入中只给出每个节点代表的区间 $[l, r]$，并不直接给出具体的划分点 $x$。
对于某次测验的考察范围 $[l, r]$，我们定义胖虎的复习代价 $f(l, r)$ 为：
从这棵大纲树的若干个节点中选出一些两两不相交的区间，使它们的并集恰好等于测验范围 $[l, r]$，所需节点数量的最小值。
（换言之，就像查询普通线段树时会把目标区间拆分成若干个节点，这里的 $f(l, r)$ 就是能够精准覆盖 $[l, r]$ 的最少节点数。）
当期末考试出分之后，春老师在群里微笑着对大家说：
同学们好，我们的期末成绩设置了达标线。
很遗憾，胖虎并没有通过达标线。看在胖虎帮老师安装Arch Linux系统的份上，春老师给胖虎一次复活考核：处理 $n$ 个物理实验样本（保证 $n$ 为偶数），编号依次为 $1,2,...,n$。春老师要求将它们两两配对进行对照实验。
如果将样本 $a$ 和 $b$ 配成一对，设 $l = \min (a, b)$，$r = \max (a, b)$，为了弄清这组对照实验背后的物理原理，胖虎必须查阅大纲中对应范围的知识，因此这一对产生的复习代价即为 $f(l, r)$。
为了能打赢春老师设置的复活赛，胖虎需要将这 $n$ 个样本划分成 $\frac{n}{2}$ 对，使得总复习代价最小，并输出一组最优的实验配对方案。如果有多组最优方案，输出任意一组即可。
糕棠虎忙着去苔冬找外国语搭子备考雅思了，于是把问题抛给了你。
输入格式
输入包含多组测试数据。
第一行包含一个整数 $T$（$1 \leq T$），表示测试数据组数。
对于每组测试数据：
- 第一行包含一个偶数 $n$（$2 \leq n \leq 5000$）。
- 接下来 $2n - 1$ 行，每行包含两个整数 $l, r$（$1 \leq l \leq r \leq n$），表示线段树中的一个节点区间 $[l, r]$。
输入保证这 $2n - 1$ 个区间恰好是一棵合法二叉线段树的所有节点区间。
此外，保证所有测试数据的 $\sum n \leq 5000$。
输出格式
对于每组测试数据：
- 第一行输出一个整数，表示最小总代价。
- 接下来输出 $\frac{n}{2}$ 行，每行输出两个不同的整数 $a,b$，表示将 $a$ 与 $b$ 配成一对。
所有输出的整数 $1，2，...，n$ 必须恰好各出现一次。
若存在多组最优方案，输出任意一组即可。
样例
输入
1
8
1 8
1 3
1 1
2 3
2 2
3 3
4 8
4 5
4 4
5 5
6 8
6 6
7 8
7 7
8 8输出
5
1 8
2 3
4 5
6 7说明
这组输出对应的配对为：
$$ [1,8], [2,3], [4,5], [6,7].$$
其中：
$$[1,8]\in S,\qquad [2,3]\in S,\qquad [4,5]\in S.$$
所以：
$$f(1,8) = 1,\qquad f(2,3) = 1,\qquad f(4,5) = 1.$$
但是[6,7]本身不是树上的节点。它需要拆成两个单点：
$$[6,7] = [6,6]\cup [7,7].$$
因此：
$$f(6,7) = 2.$$
总代价为：
$$1 + 1 + 1 + 2 = 5.$$