15468번 - Coloring Intervals 다국어

문제

For all real numbers a ≤ b, the closed interval [a, b] refers to the set of all real numbers between a and b, inclusive. For example, [3, 5] = {x ∈ \(\mathbb{R}\) | 3 ≤ x ≤ 5}.

Bob has n closed intervals, denoted [a₁, b₁], [a₂, b₂], . . ., [a_n, b_n], such that for all distinct i, j ∈ {1, 2, . . . , n},

• a_i and b_i are positive integers.
• a_i ≤ b_i. I.e., [a_i, b_i] is not empty.
• a_i ≠ b_j, a_i ≠ a_j and b_i ≠ b_j. I.e., distinct closed intervals do not have any common endpoint.

He wants to color each of the n closed intervals monochromatically such that any two distinct overlapping intervals are in different colors. Bob wonders how many colors are needed. In other words, he wants to find the minimum positive integer k such that each of the n closed intervals can be labelled with one of 1, 2, . . ., k in a way that any two distinct overlapping intervals are labelled differently. Please help him.

입력

The first line contains the number T of test cases. Each of the next T lines specifies a test case by providing n, a₁, b₁, a₂, b₂, . . ., a_n, b_n, in that order. Two consecutive numbers in a line are separated by one or more spaces.

You may assume:

• 1 ≤ T ≤ 10
• n ∈ {2, 3, . . . , 100000}
• a_i and b_i are positive integers less than or equal to 2³² − 1 for each i ∈ {1, 2, . . . , n}.

출력

For each test case, output the minimum positive integer k such that each of [a₁, b₁], [a₂, b₂], . . ., [a_n, b_n] can be labelled with one of 1, 2, . . ., k in a way that any two distinct overlapping intervals are labelled differently.

제한

힌트