Rectangles

A rectangle in the Cartesian plane is specied by a pair of coordinates (x1 , y1) and (x2 , y2) indicating its lower-left and upper-right corners, respectively (where x1 ≤ x2 and y1 ≤ y2). Given a pair of rectangles,A = ((x^A₁ , y^A₁ ), (x^A₂ ,y^A₂ )) and B = ((x^B₁ , y^B₁ ), (x^B₂ , y^B₂ )), we write A ≤ B (i.e., A "precedes" B), if x^A₂ < x^B₁ and y^A₂ < y^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₁,A₂,…,A_L) from this collection such that A₁ ≤ A₂ ≤ … ≤ A_L.

The input file 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ⁱ₁ ,yⁱ₁ ,xⁱ₂ ,yⁱ₂ (where -1000000 ≤ xⁱ₁ ≤ xⁱ₂ ≤ 1000000, -1000000 ≤ yⁱ₁ ≤ yⁱ₂ ≤ 1000000, and 1 ≤ i ≤ n), indicating the lower left and upper right corners of a rectangle. The end-of-file is denoted by asingle line containing the integer 0.

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

3
1 5 2 8
3 -1 5 4
10 10 20 20
2
2 1 4 5
6 5 8 10
0

2
1

2009 Stanford Local ACM Programming Contest