Let interval [s, t] denote the set of integers between s and t, inclusively. Given a set of n intervals A = {[si, ti]}, compute a set of intervals B (not necessary a subset of A), such that each [si, ti] ∈ A can be presented as the union (set-union) of some intervals in B. The goal is to minimize the number of intervals in B.
输入描述:
There are at most 100 test cases. Each case will consist of one integer n, following n lines each consists of si and ti, separated by a space.
1 ≤ n ≤ 1000, 0 ≤ si ≤ ti ≤ 109.
输出描述:
For each test case, print a single line containing one integer m, the number of intervals. The j-th line of the following m lines contain the j-th interval as sj and tj, the intervals can be in any order. If there are multiple solutions with the same number of intervals, any of them will be accepted.
示例1
输入
复制
2
1 2
3 4
3
1 2
3 4
1 4
7
5 9
0 6
4 8
3 7
0 5
7 9
4 6
输出
复制
2
1 2
3 4
2
1 2
3 4
5
0 5
4 6
3 7
5 8
7 9