Sau khi tác phẩm trước đây của Bessie được giới phê bình ca ngợi, cô được mời làm công việc thiết kế các bộ tranh. Cô thiết kế những bức tranh này bằng cách chọn \(1\le N\le 10^5\) hình chữ nhật có cạnh song song với các trục trên mặt phẳng, sao cho không có hai cạnh nào thẳng hàng. Biên của các hình chữ nhật này xác định biên của các miền màu trong bức tranh.

Vẫn là một nghệ sĩ tiên phong, Bessie quyết định rằng bức tranh nên giống một con bò Holstein. Cụ thể hơn, mỗi miền do các hình chữ nhật tạo thành được tô đen hoặc trắng, không có hai miền kề nhau nào cùng màu, và miền nằm ngoài tất cả các hình chữ nhật được tô trắng.

Sau khi chọn các hình chữ nhật, Bessie muốn bạn in một trong hai kết quả tùy theo tham số \(T\):

• Nếu \(T=1\), in tổng số miền.
• Nếu \(T=2\), in số miền trắng, sau đó là số miền đen.

Lưu ý: giới hạn thời gian của bài này là 4 giây, gấp đôi mức mặc định.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(T\).

Mỗi dòng trong \(N\) dòng tiếp theo mô tả một hình chữ nhật dưới dạng \((x_1,y_1),(x_2,y_2)\), trong đó \(1\le x_1<x_2\le 2N\) và \(1\le y_1<y_2\le 2N\). \((x_1,y_1)\) và \((x_2,y_2)\) lần lượt là góc dưới bên trái và góc trên bên phải của hình chữ nhật.

Bảo đảm rằng tất cả các \(x_i\) tạo thành một hoán vị của \(1\ldots 2N\), và điều tương tự cũng đúng với tất cả các \(y_i\).

Dữ liệu ra

In một số nguyên nếu \(T=1\); nếu không, in hai số nguyên cách nhau bởi dấu cách.

Phân nhóm

1. Các test 3–4 thỏa mãn \(N\le 10^3\).
2. Trong các test 5–7, không có hai biên hình chữ nhật nào giao nhau.
3. Trong các test 8–10, \(T=1\) và biên của tất cả các hình chữ nhật liên thông với nhau.
4. Trong các test 11–13, \(T=2\) và biên của tất cả các hình chữ nhật liên thông với nhau.
5. Trong các test 14–18, \(T=1\).
6. Trong các test 19–23, \(T=2\).

Ví dụ

2 1
1 1 3 3
2 2 4 4

4

5 2
1 5 3 6
5 4 7 9
4 1 8 3
9 8 10 10
2 2 6 7

4 5

Nguồn

USACO 2022 February Contest, Platinum — Paint by Rectangles: https://usaco.org/index.php?page=viewproblem2&cpid=1212

Tác giả: Andi Qu.