Trong sở thú JOI có \(2N\) con tắc kè hoa, được đánh số từ \(1\) đến \(2N\). Trong đó, \(N\) con có giới tính X và \(N\) con còn lại có giới tính Y.

Mỗi con có một màu gốc. Các màu gốc có những tính chất sau:

• \(N\) con có giới tính X có màu gốc đôi một khác nhau.
• Với mỗi con có giới tính X, có đúng một con có giới tính Y mang cùng màu gốc với nó.

Sở thú JOI đang bước vào mùa tình yêu. Mỗi con tắc kè hoa yêu một con khác. Những mối quan hệ này có các tính chất sau:

• Mỗi con yêu đúng một con khác giới tính với mình.
• Mỗi con và con mà nó yêu có màu gốc khác nhau.
• Không có hai con cùng yêu một con.

Bạn có thể tập hợp một số con tắc kè hoa để tổ chức một cuộc gặp. Với mỗi con \(s\) tham dự cuộc gặp, gọi \(t\) là con mà \(s\) yêu. Màu da của \(s\) được xác định như sau:

• Nếu \(t\) tham dự cuộc gặp, màu da của \(s\) là màu gốc của \(t\).
• Nếu \(t\) không tham dự cuộc gặp, màu da của \(s\) là màu gốc của chính \(s\).

Màu da của một con có thể thay đổi giữa các cuộc gặp. Trong mỗi cuộc gặp do bạn tổ chức, bạn có thể biết số màu da khác nhau của những con tham dự.

Cho số lượng tắc kè hoa, hãy xác định tất cả các cặp có cùng màu gốc bằng cách tổ chức không quá \(20\,000\) cuộc gặp.

Giao diện tương tác

Bạn cần nộp tệp chameleon.cpp, khai báo sử dụng chameleon.h và cài đặt hàm sau:

void Solve(int N);

Hàm được gọi đúng một lần cho mỗi bộ dữ liệu. Tham số \(N\) là số con có giới tính X, bằng một nửa tổng số con.

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

int Query(const std::vector<int> &p);
void Answer(int a, int b);

Mỗi lần gọi Query(p) tổ chức một cuộc gặp với danh sách các con tham dự là p. Hàm trả về số màu da khác nhau trong cuộc gặp đó.

• Mỗi phần tử của p phải là số nguyên từ \(1\) đến \(2N\). Vi phạm điều kiện này sẽ nhận Wrong Answer [1].
• Các phần tử của p phải đôi một khác nhau. Vi phạm điều kiện này sẽ nhận Wrong Answer [2].
• Không được gọi Query quá \(20\,000\) lần. Vi phạm điều kiện này sẽ nhận Wrong Answer [3].

Danh sách p có thể rỗng; một lần gọi như vậy vẫn được tính là một lần gọi Query và trả về \(0\).

Mỗi lần gọi Answer(a, b) thông báo rằng con \(a\) và con \(b\) có cùng màu gốc.

• Phải có \(1 \le a \le 2N\) và \(1 \le b \le 2N\). Vi phạm điều kiện này sẽ nhận Wrong Answer [4].
• Mỗi chỉ số chỉ được xuất hiện một lần trong toàn bộ các tham số của tất cả lời gọi Answer; hai chỉ số trong cùng một lời gọi cũng phải khác nhau. Vi phạm điều kiện này sẽ nhận Wrong Answer [5].
• Nếu \(a\) và \(b\) có màu gốc khác nhau, chương trình nhận Wrong Answer [6].
• Phải gọi Answer đúng \(N\) lần. Khi Solve kết thúc, nếu số lần gọi khác \(N\), chương trình nhận Wrong Answer [7].

Bạn có thể cài đặt các hàm phụ và sử dụng biến toàn cục. Chương trình không được đọc đầu vào chuẩn, ghi ra đầu ra chuẩn hoặc giao tiếp với các tệp bằng bất kỳ cách nào. Bạn được phép ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Dữ liệu vào

Dữ liệu sau dành cho trình chấm mẫu grader.cpp. Trình chấm mẫu và mã nguồn mẫu được cung cấp trong gói tệp hỗ trợ chính thức.

N
Y_1 ... Y_{2N}
C_1 ... C_{2N}
L_1 ... L_{2N}

Với \(1 \le i \le 2N\):

• \(Y_i\) biểu diễn giới tính của con \(i\): \(0\) là X và \(1\) là Y.
• \(C_i\) là màu gốc của con \(i\), được biểu diễn bởi một số nguyên từ \(1\) đến \(N\).
• \(L_i\) là chỉ số của con mà con \(i\) yêu.

Chương trình của bạn nhận thông tin qua giao diện tương tác ở trên, không trực tiếp đọc các mảng này.

Dữ liệu ra

Chương trình của bạn thông báo các cặp bằng Answer.

Khi chương trình kết thúc bình thường, trình chấm mẫu ghi kết quả ra đầu ra chuẩn như sau:

• Nếu câu trả lời đúng, trình chấm mẫu ghi số lần gọi Query, theo dạng như Accepted: 100.
• Nếu câu trả lời sai, trình chấm mẫu ghi loại lỗi, theo dạng như Wrong Answer [1].

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

Ràng buộc

Các dữ liệu thỏa mãn những điều kiện sau, với \(Y,C,L\) được định nghĩa trong phần dữ liệu vào cho trình chấm mẫu:

• \(2 \le N \le 500\).
• \(0 \le Y_i \le 1\) với \(1 \le i \le 2N\).
• \(1 \le C_i \le N\) với \(1 \le i \le 2N\).
• Với mỗi \(j\) (\(1 \le j \le N\)), có đúng một \(i\) (\(1 \le i \le 2N\)) thỏa mãn \(Y_i=0\) và \(C_i=j\).
• Với mỗi \(j\) (\(1 \le j \le N\)), có đúng một \(i\) (\(1 \le i \le 2N\)) thỏa mãn \(Y_i=1\) và \(C_i=j\).
• \(1 \le L_i \le 2N\) với \(1 \le i \le 2N\).
• \(Y_i \ne Y_{L_i}\) với \(1 \le i \le 2N\).
• \(C_i \ne C_{L_i}\) với \(1 \le i \le 2N\).
• \(L_k \ne L_l\) với \(1 \le k < l \le 2N\).

Phân nhóm

1. (4 điểm) \(L_{L_i}=i\) với \(1 \le i \le 2N\).
2. (20 điểm) \(N \le 7\).
3. (20 điểm) \(N \le 50\).
4. (20 điểm) \(Y_i=0\) với \(1 \le i \le N\).
5. (36 điểm) Không có ràng buộc bổ sung.

Ví dụ giao tiếp

4
1 0 1 0 0 1 1 0
4 4 1 2 1 2 3 3
4 3 8 7 6 5 2 1

Với dữ liệu trên, một quá trình tương tác có thể diễn ra như sau. Trình chấm gọi Solve(4), sau đó chương trình thực hiện các lời gọi theo đúng thứ tự trong bảng.

4
1 1 1 0 0 1 0 0
3 1 4 3 1 2 2 4
5 7 4 3 1 8 2 6

Đây là tệp sample-02.txt trong gói dữ liệu chính thức. Dữ liệu này thỏa mãn ràng buộc của nhóm \(1\).

4
0 0 0 0 1 1 1 1
4 3 2 1 2 3 4 1
6 8 7 5 2 3 4 1

Đây là tệp sample-03.txt trong gói dữ liệu chính thức. Dữ liệu này thỏa mãn ràng buộc của nhóm \(4\).

Nguồn

Bản dịch tiếng Việt từ đề chính thức bằng tiếng Anh của Ủy ban Olympic Tin học Nhật Bản, JOI 2019/2020, Trại huấn luyện mùa xuân, ngày thi thứ 2. Các tệp ví dụ bổ sung lấy từ gói dữ liệu chính thức. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.