Mô tả và yêu cầu

9/30/21, 10:19 PM Nested Dolls - VNOJ: VNOI Online Judge
Nested Dolls

Time Limit: 1.0s Memory Limit: 256M

"Dilworth" có một bộ sưu tập các con búp bê Nga. Búp bê với chiều rộng w 1 và chiều cao h1 sẽ nằm trong
được con búp bê chiều rộng w 2 và chiều cao h2 nếu w 1 < w 2 và h1 < h2 .

Tính số lớp búp bê bao nhau ít nhất mà có thể tạo ra được từ các búp bê ban đầu.

Dữ liệu vào

Dòng đầu là số test (1 ≤ t ≤ 20.

Mỗi test gồm:

số nguyên m (1 ≤ m ≤ 20000), số lượng búp bê ban đầu.
Dòng tiếp theo là 2m số nguyên w 1,h1 ,w 2,h2 ,...,w m ,hm , là chiều rộng và chiều cao của con búp bê
thứ i (1 ≤ w i,hi ≤ 10000 .

Dữ liệu ra

Ghi số lớp búp bê bao nhau ít nhất có thể trên một dòng cho từng test.

Sample Input

4
3
20 30 40 50 30 40
4
20 30 10 10 30 20 40 50
3
10 30 20 20 30 10
4
10 10 20 30 40 50 39 51

Sample Output

https://oj.vnoi.info/problem/MDOLLS 1/2

9/30/21, 10:19 PM Nested Dolls - VNOJ: VNOI Online Judge

1
2
3
2

https://oj.vnoi.info/problem/MDOLLS 2/2