题目描述

你被给定一系列关于重要的历史事件的演讲，每件事对应一场演讲。

它们不按顺序排列，每件历史事件持续一个时间段 $[a_i,b_i]$。

如果两件事的时间有共同区间，我们说它们是有关联的，把关于有关联的历史事件的演讲排的彼此靠近能使课程更便于理解。

此外，不相关的演讲必须按历史事件的发生时间排序（如果 A 在 B 之前发生，且 AB 不相关，那么关于 A 的演讲必须在 B 之前进行）。

找出最小的整数 $k$ （$k \ge 0$） 和一个演讲的顺序，使得排序后任意两场相关的演讲之间的间隔不超过 $k$（第 $i$ 场演讲和第 $j$ 场演讲之间的间隔是 $|i-j|$）。

输入格式

第一行包括数据组数 $T$。

每组数据的第一行是一个数 $n$，接下来 $n$ 行每行包括两个整数 $[a_i,b_i]$，区间两两不相同。

输出格式

每组数据答案的第一行是一个最小值 $k$，接下来 $n$ 行按顺序列举排列后的演讲的历史区间（与输入中的格式一样），使得任意两个相关的演讲间隔不超过 $k$。

切记将不相关的演讲按时间顺序排列！

1 
3 
1 6 
2 3 
4 5 

1 
2 3 
1 6 
4 5 

样例说明

共有三个历史事件，其中 $1,2$，$1,3$ 是相关的，$2,3$ 不相关，且 $2$ 在 $3$ 之前发生，所以 $2$ 应该排在 $3$ 的前面。

对于相关的历史事件，$1$ 与 $2$ 在排列后的位置是 $2$ 和 $1$，间隔为 $1$,$1$ 与 $3$ 在排列后的位置为 $2$ 与 $3$，间隔为 $1$,所以此时 $k$ 最小为 $1$，该排法最优。

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 5 \times 10^4$，$-10^9 \le a_i \le b_i \le 10^9$。