题目描述

You are to give a series of lectures on important historical events, one event per lecture, in some order. Each event lasted for some time interval $[a_i, b_i].$ We say that two events are related if their intervals have a common point. It would be convenient to schedule lectures on related events close to each other. Moreover, lectures on unrelated events should be given in the order in which the events have taken place (if an event A preceded an unrelated event $B$ , then the lecture on A should precede the lecture on $B)$ .

Find the minimum integer $k \ge 0$ and an order of the lectures such that any two related events are scheduled at most $k$ lectures apart from each other (lectures number $i$ and $j$ are considered to be $|i−j|$ lectures apart).

输入格式

The first line of input contains the number of test cases $t$ . The descriptions of the test cases follow:

The first line of each test case contains the number $n (1 \le n \le 50000)$ . Each of the next $n$ lines contains two integers $a_i$ and $b_i (-10^9 \le a_i \le b_i \le 10^9)$ - the ends of the i-th interval. The intervals are pairwise different.

输出格式

Print the answers to the test cases in the order in which they appear in the input. The first line of the answer to each test case should contain the minimum value of $k$ . The next $n$ lines should list the intervals (in the same format as in the input) in an order such that any two related events are scheduled at most $k$ lectures apart. Remember to put any unrelated intervals in the proper order!

题目大意

给定 $n$ 个区间，第 $i$ 个区间为 $[a_i,b_i]$。你需要把这些区间按某种顺序排列，使得两个区间如果没有交点，则左端点更小的区间需要排在前面。

设第 $i$ 个区间排在第 $p_i$ 个位置，定义区间 $i$ 与 $j$ 之间的距离为 $|p_i-p_j|$。令 $k$ 为任意两个相交的区间之间的最大距离，你需要最小化 $k$，并输出一组对应的合法顺序。

对于 $100\%$ 的数据，满足 $1\leq n\leq 5\times 10^4$，$0\leq|a_i|,|b_i|\leq10^9$。

1
3
1 6
2 3
4 5

1
2 3
1 6
4 5

提示

Time limit: 10 s, Memory limit: 128 MB.

感谢 hht2006 提供的 Special Judge。