Trong thời gian được cách ly để bảo vệ khỏi đợt bùng phát COWVID-19, những con bò của Nông dân John đã nghĩ ra một cách mới để bớt buồn chán: nghiên cứu vật lý nâng cao! Thật vậy, chúng thậm chí còn khám phá được một hạt hạ nguyên tử mới và đặt tên cho nó là "hạt moo".

Hiện tại, những con bò đang tiến hành một thí nghiệm với \(N\) hạt moo (\(1 \leq N \leq 10^5\)). Hạt \(i\) có một "spin" được mô tả bởi hai số nguyên \(x_i\) và \(y_i\) trong phạm vi \(-10^9 \ldots 10^9\), kể cả hai đầu mút. Đôi khi hai hạt moo tương tác với nhau. Điều này chỉ có thể xảy ra với hai hạt có spin \((x_i, y_i)\) và \((x_j, y_j)\) nếu \(x_i \leq x_j\) và \(y_i \leq y_j\). Trong những điều kiện này, có khả năng đúng một trong hai hạt biến mất (và hạt còn lại không bị ảnh hưởng). Tại mỗi thời điểm, nhiều nhất một tương tác sẽ xảy ra.

Những con bò muốn biết số hạt moo nhỏ nhất có thể còn lại sau một chuỗi tương tác tùy ý.

Dữ liệu vào

Tệp moop.in:

Dòng đầu tiên chứa một số nguyên \(N\), là số hạt moo ban đầu. Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên cách nhau bởi dấu cách, biểu thị spin của một hạt. Mỗi hạt có một spin riêng biệt.

Dữ liệu ra

Tệp moop.out:

In một số nguyên duy nhất, là số hạt moo nhỏ nhất có thể còn lại sau một chuỗi tương tác tùy ý.

Phân nhóm

• Các test 3–6 thỏa mãn \(N \leq 1000\).
• Các test 7–12 không có ràng buộc bổ sung.

Ví dụ

4
1 0
0 1
-1 0
0 -1

1

3
0 0
1 1
-1 3

2

Nguồn

USACO 2020 US Open Contest, Silver — The Moo Particle

Tác giả bài: Dhruv Rohatgi.