18749번 - Hit 스페셜 저지다국어

Place at most n integer points on the number line in such a way that each of the given n segments [l_i, r_i] 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 ≤ 10⁵), denoting the number of test cases.

Each test case is described with an integer n (1 ≤ n ≤ 10⁵), followed by n lines containing two integers l_i and r_i each (−10⁹ ≤ l_i < r_i ≤ 10⁹), denoting a segment containing points l_i, l_i + 1, . . . , r_i. Segments may coincide.

The sum of n over all test cases does not exceed 10⁵.

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 x_i (−10⁹ ≤ x_i ≤ 10⁹), denoting the coordinates of the points you place.