7657번 - Rectangles 다국어

문제

A rectangle in the Cartesian plane is specified by a pair of coordinates (\(x_1\), \(y_1\)) and (\(x_2\), \(y_2\)) indicating its lower-left and upper-right corners, respectively (where \(x_1\) ≤ \(x_2\) and \(y_1\) ≤ \(y_2\)). Given a pair of rectangles, \(A\) = ((\(x_1^A\), \(y_1^A\)), (\(x_2^A\), \(y_2^A\))) and \(B\) = ((\(x_1^B\), \(y_1^B\)), (\(x_2^B\), \(y_2^B\))), we write \(A\) ⪯ \(B\) (i.e., \(A\) "precedes" \(B\)), if

\(x_2^A\) < \(x_1^B\) and \(y_2^A\) < \(y_1^B\).

In this problem, you are given a collection of rectangles located in the two-dimension Euclidean plane. Find the length L of the longest sequence of rectangles (\(A_1\), \(A_2\), ..., \(A_L\)) from this collection such that

\(A_1\) ⪯ \(A_2\) ⪯ ... ⪯ \(A_L\).

입력

The input file will contain multiple test cases. Each test case will begin with a line containing a single integer \(n\) (where 1 ≤ \(n\) ≤ 1000), indicating the number of input rectangles. The next \(n\) lines each contain four integers \(x_1^i\) \(y_1^i\) \(x_2^i\) \(y_2^i\) (where −1000000 ≤ \(x_1^i\) ≤ \(x_2^i\) ≤ 1000000, −1000000 ≤ \(y_1^i\) ≤ \(y_2^i\) ≤ 1000000, and 1 ≤ \(i\) ≤ \(n\)), indicating the lower left and upper right corners of a rectangle. The end-of-file is denoted by a single line containing the integer 0.

출력

For each input test case, print a single integer indicating the length of the longest chain.

제한

힌트