题目描述

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!

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。