Phòng thí nghiệm của giáo sư JOI đang nghiên cứu \(N\) loại khoáng vật. Mỗi loại có hai lát mẫu, tổng cộng có \(2N\) lát mẫu được đánh số từ \(1\) đến \(2N\).

Một hôm, trợ lý Bitaro làm rơi chiếc hộp đựng các lát mẫu. Cậu không còn biết những lát mẫu nào thuộc cùng một loại khoáng vật.

Phòng thí nghiệm có một thiết bị đo các bước sóng mà khoáng vật hấp thụ, qua đó đếm được số loại khoáng vật khác nhau trong số các lát mẫu đang đặt trong thiết bị. Bitaro muốn xác định \(N\) cặp lát mẫu cùng loại. Ban đầu, thiết bị không chứa lát mẫu nào. Cậu có thể thực hiện các thao tác sau:

• Đưa một lát mẫu vào thiết bị và biết được số loại khoáng vật khác nhau đang có trong thiết bị.
• Lấy một lát mẫu ra khỏi thiết bị và biết được số loại khoáng vật khác nhau đang có trong thiết bị.

Để giáo sư JOI không phát hiện ra sự cố, Bitaro chỉ có thể thực hiện tổng cộng không quá \(1\,000\,000\) thao tác.

Hãy viết chương trình nhận số loại khoáng vật và sử dụng thiết bị để xác định tất cả các cặp lát mẫu cùng loại.

Chi tiết cài đặt

Bạn cần nộp một tệp minerals.cpp, khai báo #include "minerals.h" và cài đặt hàm sau:

void Solve(int N);

Hàm này được gọi đúng một lần cho mỗi bộ dữ liệu. Tham số N là số loại khoáng vật.

Chương trình của bạn có thể gọi các hàm sau do trình chấm cung cấp:

int Query(int x);

Hàm này lấy lát mẫu x ra khỏi thiết bị nếu nó đang ở trong thiết bị; ngược lại, đưa lát mẫu đó vào thiết bị. Sau thao tác, hàm trả về số loại khoáng vật khác nhau đang có trong thiết bị.

• Phải có \(1 \le x \le 2N\). Nếu không, chương trình bị đánh giá Wrong Answer [1].
• Không được gọi Query quá \(1\,000\,000\) lần. Nếu vi phạm, chương trình bị đánh giá Wrong Answer [2].

void Answer(int a, int b);

Hàm này thông báo rằng lát mẫu a và lát mẫu b thuộc cùng một loại khoáng vật.

• Phải có \(1 \le a \le 2N\) và \(1 \le b \le 2N\). Nếu không, chương trình bị đánh giá Wrong Answer [3].
• Trong toàn bộ các đối số a và b của tất cả các lần gọi, không giá trị nào được xuất hiện quá một lần. Nếu vi phạm, chương trình bị đánh giá Wrong Answer [4].
• Nếu hai lát mẫu được chỉ định khác loại, chương trình bị đánh giá Wrong Answer [5].
• Phải gọi Answer đúng \(N\) lần. Nếu khi Solve kết thúc mà số lần gọi không bằng \(N\), chương trình bị đánh giá Wrong Answer [6].

Biên dịch và chạy thử

Gói chương trình mẫu gồm trình chấm thử grader.cpp, tệp khai báo minerals.h và tệp mã nguồn mẫu minerals.cpp. Để chạy thử, đặt ba tệp trong cùng một thư mục và biên dịch grader.cpp cùng với minerals.cpp thành chương trình grader.

Dữ liệu vào của trình chấm thử

Trình chấm thử đọc dữ liệu theo định dạng:

N
X_1 Y_1
...
X_N Y_N

Với mỗi \(i\) từ \(1\) đến \(N\), lát mẫu \(X_i\) và lát mẫu \(Y_i\) thuộc cùng một loại khoáng vật.

Dữ liệu ra của trình chấm thử

Khi chương trình kết thúc, trình chấm thử ghi thông tin sau ra đầu ra chuẩn:

• Nếu chương trình của bạn được đánh giá đúng, trình chấm thử ghi số lần gọi Query, chẳng hạn Accepted: 100.
• Nếu chương trình của bạn bị đánh giá sai, trình chấm thử ghi loại lỗi, chẳng hạn Wrong Answer [1].

Nếu chương trình vi phạm nhiều loại lỗi, trình chấm thử chỉ thông báo một loại.

Ràng buộc

Các giá trị \(X_i,Y_i\) được định nghĩa trong phần dữ liệu vào của trình chấm thử.

• \(1 \le N \le 43\,000\).
• \(1 \le X_i \le 2N\) với \(1 \le i \le N\).
• \(1 \le Y_i \le 2N\) với \(1 \le i \le N\).
• \(X_i \ne X_j\) với \(1 \le i < j \le N\).
• \(Y_i \ne Y_j\) với \(1 \le i < j \le N\).
• \(X_i \ne Y_j\) với \(1 \le i \le N\) và \(1 \le j \le N\).

Phân nhóm

1. \(6\) điểm: \(N \le 100\).
2. \(25\) điểm: \(N \le 15\,000\); \(1 \le X_i \le N\) và \(N+1 \le Y_i \le 2N\) với mọi \(1 \le i \le N\).
3. \(9\) điểm: \(N \le 15\,000\).
4. \(30\) điểm: \(N \le 38\,000\).
5. \(5\) điểm: \(N \le 39\,000\).
6. \(5\) điểm: \(N \le 40\,000\).
7. \(5\) điểm: \(N \le 41\,000\).
8. \(5\) điểm: \(N \le 42\,000\).
9. \(10\) điểm: Không có ràng buộc bổ sung.

Ví dụ giao tiếp

Dưới đây là một dữ liệu vào của trình chấm thử và các lời gọi hàm tương ứng.

4
1 5
2 6
3 4
7 8

Nguồn

JOI 2018/2019, trại huấn luyện mùa xuân, ngày thi thứ 4 (23/03/2019). Bản dịch tiếng Việt từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản. Trang công bố cấp phép nội dung theo CC BY-SA 4.0; bản dịch giữ cùng giấy phép.