Chính phủ Siruseri vừa xây dựng một trung tâm hội nghị mới. Nhiều công ty muốn thuê hội trường của trung tâm để tổ chức hội nghị.

Một khách hàng chỉ đồng ý thuê nếu được sử dụng riêng hội trường trong toàn bộ thời gian diễn ra hội nghị của mình. Trưởng bộ phận tiếp thị của trung tâm quyết định cho càng nhiều khách hàng khác nhau thuê càng tốt. Có thể có nhiều cách lựa chọn đáp ứng mục tiêu này.

Các công ty được đánh số theo thứ tự gửi yêu cầu thuê. Một tập yêu cầu được xem là tập ứng viên nếu có số lượng công ty lớn nhất có thể mà không có hai hội nghị nào trùng ngày. Để bảo đảm công bằng, trưởng bộ phận tiếp thị sắp xếp các số hiệu công ty trong mỗi tập ứng viên theo thứ tự tăng dần, rồi chọn danh sách nhỏ nhất theo thứ tự từ điển.

Thứ tự từ điển được định nghĩa như sau: danh sách \(L_1\) nhỏ hơn danh sách \(L_2\) nếu \(L_1\) là tiền tố của \(L_2\), hoặc tại vị trí đầu tiên \(j\) mà hai danh sách khác nhau, ta có \(L_1[j] < L_2[j]\).

Hội trường chỉ có thể được cho một công ty thuê trong mỗi ngày. Ngày bắt đầu và ngày kết thúc đều thuộc thời gian thuê; vì vậy, hai yêu cầu có ngày kết thúc của yêu cầu này bằng ngày bắt đầu của yêu cầu kia không thể cùng được chấp nhận.

Hãy xác định tập công ty được thuê hội trường theo quy tắc trên.

Dữ liệu vào

Dòng đầu chứa số nguyên \(N\), số công ty đã gửi yêu cầu thuê hội trường.

Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên là ngày bắt đầu và ngày kết thúc hội nghị của công ty \(i\).

Dữ liệu ra

Dòng đầu chứa số nguyên \(M\), số công ty lớn nhất có thể được thuê hội trường.

Dòng thứ hai chứa \(M\) số nguyên là số hiệu các công ty, viết theo thứ tự tăng dần, trong tập ứng viên nhỏ nhất theo thứ tự từ điển.

Ràng buộc

• \(1 \le N \le 200000\).
• Với mỗi yêu cầu, ngày bắt đầu không nhỏ hơn \(1\), ngày kết thúc không lớn hơn \(10^9\), và ngày bắt đầu không lớn hơn ngày kết thúc.

Phân nhóm

Mỗi phân nhóm được chấm độc lập theo kiểu tất cả hoặc không: bạn chỉ nhận điểm của nhóm khi đúng toàn bộ test trong nhóm. Điểm trong bảng là phần điểm cộng thêm trên LQDOJ; nhóm sau bao gồm lại các test thỏa điều kiện của nhóm trước.

Ví dụ

4
4 9
9 11
13 19
10 17

2
1 3

Nguồn

Asia-Pacific Informatics Olympiad 2009 — Convention (The Siruseri Convention Centre), đề tiếng Anh phiên bản 1.1.