9001번 - Rectangle Coloring 다국어

You are given n axis-parallel rectangles on a plane. Here, an axis -parallel rectangle is a rectangle whose edges are parallel to either x -axis or y -axis. You are to find the number of colors to paint the given n rectangles according to the following rules:

1. 1. Each rectangle has to be painted with one color.
2. 2. A pair of intersecting rectangles must have the same color. Two rectangles are intersecting if their intersection is not empty when we regard a rectangle as a set of points including the boundary.
3. 3. A rectangle R_a must have the same color as R_b if there is a sequence of rectangles R_a = R_i1, R_i2, …,R_ik = R_b such that R_ij and R_ij+1 are intersecting for all 1≤ j < k ; otherwise, they must have different colors. For instance, rectangle R₉ in the following figure must have the same color as R_4, R_5, R₈, and have a different color from R_1, R₂, R₃, R₆, R₇.

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case begins with a line containing an integer N , 1≤ N ≤ 200 , that represents the number of rectangles in the test case. Each of the following N lines contains four positive integers x₁ , y₁ , x₂ , and y₂, 1 ≤ x₁,y₁,x₂,y₂ ≤ 10000 , representing a rectangle. (x₁ ,y₁) and (x₂ , y₂) are the (x, y) -coordinates of the lower - left and upper -right corners of the rectangle, respectively. The four integers are delimited by one or more spaces. From the N +3 -th line, the remaining test cases are listed in the same manner as above.

The output should contain the number of colors, one per line.