1695 - Pyy Loves Intervals

Time Limit: 3s Memory Limit: 128MB

Submissions: 37 Solved: 11
Description

Pyy is good at math. Now he has n close intervals, each interval begins and ends with positive integers.

He wants to find the union of these intervals, but these days he is busy preparing for CET. So he wants your help. Please calculate the union of these intervals.

That is, for n given intervals:

 

You should calculate the union set S:

It's easy to find that there may be more than one non-intersect intervals in S. Please print the answer following the description below.

 

 

Input

The first line of input file is a positive integer T (T<=20), meaning there are T test cases.

    For each test case:

    The first line is a positive integer n(n<=1e5), meaning there are n intervals in this test case.

    For the following n lines, each line has two integers l and r, which stand for an interval  [l, r]. (l<=r, 1<=l, r<=1e8), please notice that l may be equal to r.

 

Output

For each test case, you should print your answer with the format as following.

    The first line is "Case #x:", where x is the case number beings from 1.

    The second line is an integer m, which means there are m non-intersect interval(s) in the union set.

    In the third line, you should print the m interval(s) in the union set in non-decreasing order. In each interval, you should print one dash("-",no quote) between the left and right end point,and print a space between every two intervals.

 

    We guarantee that there always be a solution, in the other words, the union set wouldn't be empty.

Sample Input
3
3
1 2
2 3
3 4
3
1 2
3 4
5 6
4
1 4
2 3
6 6
7 7
Sample Output
Case #1:
1
1-4
Case #2:
3
1-2 3-4 5-6
Case #3:
3
1-4 6-6 7-7
Hint
Source
skyword