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ó $2$ lát mẫu. Tổng cộng có $2N$ lát mẫu, được đánh số từ $1$ đến $2N$.

Một ngày nọ, trợ lý Bitaro làm rơi hộp chứa $2N$ lát mẫu, nên 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ị có thể đếm số loại khoáng vật trong các lát mẫu được đặt vào, bằng cách đo bước sóng mà mỗi khoáng vật hấp thụ. Bitaro định xác định $N$ cặp lát mẫu cùng loại trong $2N$ lát mẫu. Ban đầu, thiết bị không chứa lát mẫu nào. Bitaro có thể thực hiện các thao tác sau:

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

Để Giáo sư JOI không phát hiện ra rắc rối mà Bitaro gây ra, Bitaro chỉ có thể thực hiện tổng cộng tối đa $1\,000\,000$ thao tác này.

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.

Tệp có tên minerals.cpp. Tệp phải cài đặt hàm sau. Chương trình phải bao gồm minerals.h.

• void Solve(int N)

Hàm này được gọi đúng một lần cho mỗi bộ dữ liệu kiểm thử.

• Tham số N biểu diễn $N$, số loại khoáng vật.

Chương trình của bạn có thể gọi các hàm sau.

• int Query(int x)

Với chỉ số lát mẫu mà bạn chỉ định, hàm này lấy lát mẫu đó ra khỏi thiết bị nếu nó đang ở trong thiết bị; nếu không, hàm đặt nó vào thiết bị. Sau đó, hàm trả về số loại khoáng vật trong thiết bị.

• Bạn chỉ định chỉ số $x$ của lát mẫu qua tham số x. Phải thỏa mãn $1 \le x \le 2N$. Nếu không, chương trình bị đánh giá là Wrong Answer [1].

• Hàm Query không được gọi quá $1\,000\,000$ lần. Nếu không, chương trình bị đánh giá là Wrong Answer [2].

• void Answer(int a, int b)

Bạn dùng hàm này để trả lời các cặp lát mẫu cùng loại khoáng vật.

• Các tham số a và b cho biết lát mẫu thứ $a$ và lát mẫu thứ $b$ thuộc cùng một loại khoáng vật. Phải thỏa mãn $1 \le a \le 2N$ và $1 \le b \le 2N$. Nếu không, chương trình bị đánh giá là Wrong Answer [3]. Nếu một giá trị xuất hiện nhiều hơn một lần khi tính chung cả a và b, chương trình bị đánh giá là Wrong Answer [4]. Nếu chỉ định hai lát mẫu khác loại khoáng vật, chương trình bị đánh giá là Wrong Answer [5].

Hàm Answer phải được gọi đúng $N$ lần. Nếu khi hàm Solve kết thúc, số lần gọi hàm Answer không bằng $N$, chương trình bị đánh giá là Wrong Answer [6].

Lưu ý quan trọng

• Chương trình có thể cài đặt các hàm khác để sử dụng nội bộ hoặc dùng biến toàn cục.
• Chương trình không được sử dụng đầu vào chuẩn và đầu ra chuẩn. Chương trình không được giao tiếp với các tệp khác bằng bất kỳ phương thức nào. Tuy nhiên, chương trình có thể xuất thông tin gỡ lỗi ra luồng lỗi chuẩn.

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

Bạn có thể tải từ trang web cuộc thi một tệp nén chứa trình chấm mẫu để kiểm thử chương trình. Tệp nén cũng chứa một tệp mã nguồn mẫu cho chương trình của bạn.

Trình chấm mẫu là tệp grader.cpp. Để kiểm thử chương trình, đặt grader.cpp, minerals.cpp và minerals.h trong cùng một thư mục, rồi chạy lệnh sau để biên dịch.

g++ -std=gnu++14 -O2 -o grader grader.cpp minerals.cpp

Khi biên dịch thành công, tệp thực thi grader được tạo ra.

Lưu ý rằng trình chấm thực tế khác với trình chấm mẫu. Trình chấm mẫu chạy dưới dạng một tiến trình duy nhất, đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn.

Dữ liệu vào cho trình chấm mẫu

Trình chấm mẫu đọc dữ liệu sau từ đầu vào chuẩn.

$$ \begin{array}{l} N \\ X_1\ Y_1 \\ \vdots \\ X_N\ Y_N \end{array} $$

$X_i$ và $Y_i$ ($1 \le i \le N$) cho biết lát mẫu thứ $X_i$ và lát mẫu thứ $Y_i$ thuộc cùng một loại khoáng vật.

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

Khi chương trình kết thúc thành công, trình chấm mẫu ghi thông tin sau ra đầu ra chuẩn (dấu ngoặc kép chỉ dùng để làm rõ).

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

Nếu chương trình mắc nhiều loại lỗi trả lời sai, trình chấm mẫu chỉ báo một trong số đó.

Giới hạn

Xem mục “Dữ liệu vào cho trình chấm mẫu” để biết định nghĩa của $X_i$ và $Y_i$.

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

Nhiệm vụ con

1. (6 điểm) $N \le 100$.
2. (25 điểm) $N \le 15\,000$, $1 \le X_i \le N$, $N+1 \le Y_i \le 2N$ ($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ó giới hạn bổ sung.

Ví dụ

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

Dữ liệu vào 1

4
1 5
2 6
3 4
7 8

Các lời gọi mẫu