Chọn sách

Thư viện trường học của bạn An có $n$ quyển sách, mỗi quyển sách có dạng hình chữ nhật. Các quyển sách được đánh số thứ tự từ 1 đến $n$. Quyển sách thứ $i$ $(i = 1, 2, \dots, n)$ có chiều dài là $d_i$, chiều rộng là $r_i$ (đơn vị độ dài). Bạn An muốn chọn một số quyển sách trong $n$ quyển sách để xếp thành một chồng sao cho quyển sách được xếp ở trên có kích thước nhỏ hơn quyển sách được xếp ở dưới, tức là nếu quyển sách $i$ được xếp trên quyển sách $j$ thì $d_i < d_j$ và $r_i < r_j$.

Yêu cầu: Hãy đưa ra số sách lớn nhất mà bạn An có thể chọn để xếp được chồng sách theo yêu cầu trên. Ta gọi số quyển sách nhiều nhất có thể chọn được là $S$.

Dữ liệu cho trong tệp văn bản ChonSach.Inp gồm:

• Dòng đầu tiên ghi số nguyên dương $n$ $(2 \le n \le 2 \times 10^5)$ là số lượng quyển sách.
• Dòng thứ $i$ trong $n$ dòng tiếp theo ghi 2 số nguyên dương $d_i$ và $r_i$ $(1 \le d_i, r_i \le 10^8)$ tương ứng là chiều dài và chiều rộng của quyển sách thứ $i$.

Kết quả ghi ra tệp văn bản ChonSach.Out số nguyên $S$ tìm được.

• Có 25% số test ứng với 25% số điểm thỏa mãn $2 \le n \le 200$ và $S \le 2$;
• Có 25% số test ứng với 25% số điểm thỏa mãn $2 \le n \le 2 \times 10^3$; $d_i \ne d_j$ và $r_i \ne r_j$ với mọi cặp $i \ne j$; $1 \le i, j \le n$;
• Có 25% số test ứng với 25% số điểm thỏa mãn $2 \times 10^3 < n \le 2 \times 10^5$; $d_i \ne d_j$ và $r_i \ne r_j$ với mọi cặp $i \ne j$; $1 \le i, j \le n$;
• Có 25% số test ứng với 25% số điểm còn lại thỏa mãn $2 \times 10^3 < n \le 2 \times 10^5$.