| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 114 | 35 | 27 | 37.500% |
Place at most n integer points on the number line in such a way that each of the given n segments [li, ri] contains at least one point, and the largest number of points contained inside one of the given segments is as small as possible.
The first line contains a single integer t (1 ≤ t ≤ 105), denoting the number of test cases.
Each test case is described with an integer n (1 ≤ n ≤ 105), followed by n lines containing two integers li and ri each (−109 ≤ li < ri ≤ 109), denoting a segment containing points li, li + 1, . . . , ri. Segments may coincide.
The sum of n over all test cases does not exceed 105.
For each test case, display the largest number of points inside one of the given segments in your placement, followed by the number of points you place k (1 ≤ k ≤ n), followed by k distinct integers xi (−109 ≤ xi ≤ 109), denoting the coordinates of the points you place.
4 4 0 1 2 3 4 5 3 5 5 0 70 0 10 20 30 40 50 60 70 8 -1 7 -2 -1 -9 -7 -8 9 -9 -7 -2 4 -7 4 3 9 5 0 1 0 2 2 3 3 5 4 5
1 3 1 2 5 4 4 10 30 50 70 2 3 -9 -1 9 2 3 1 3 5