Xét một đồ thị có hướng gồm \(n\) đỉnh, đánh số \(1,2,\ldots,n\). Đồ thị được gọi là một tournament nếu giữa mỗi cặp đỉnh có đúng một cạnh theo một trong hai hướng. Nói cách khác, với hai đỉnh phân biệt \(u,v\), có cạnh từ \(u\) tới \(v\) hoặc có cạnh từ \(v\) tới \(u\).

Một chu trình Hamilton là dãy \(c_1,c_2,\ldots,c_n\) đi qua mọi đỉnh rồi quay lại điểm xuất phát. Với mọi \(1\le i<n\), phải có cạnh từ \(c_i\) tới \(c_{i+1}\); ngoài ra phải có cạnh từ \(c_n\) tới \(c_1\).

Bạn được tự do xây dựng một tournament gồm \(n\) đỉnh. Sau đó, bộ chấm bí mật xáo trộn số hiệu các đỉnh. Hãy tìm một chu trình Hamilton trong đồ thị đã bị xáo trộn bằng cách truy vấn hướng cạnh.

Hình 1: Một tournament trước và sau khi số hiệu đỉnh bị xáo trộn; chu trình Hamilton được tô nổi bật.

Tương tác

Đây là bài tương tác. Ban đầu, đọc hai số nguyên \(n,t\), lần lượt là số đỉnh và số bộ test.

Tiếp theo, in \(n\) dòng mô tả tournament. Dòng thứ \(u\) phải gồm đúng \(n\) ký tự 0 hoặc 1; ký tự thứ \(v\) là 1 khi có cạnh từ \(u\) tới \(v\). Không được có cạnh từ một đỉnh tới chính nó, và giữa mỗi cặp đỉnh phân biệt phải có đúng một cạnh.

Sau đó có \(t\) bộ test. Mỗi bộ test dùng cùng tournament do bạn cung cấp, nhưng số hiệu đỉnh được xáo trộn độc lập và được giữ bí mật.

Để truy vấn, in:

? u v

trong đó \(1\le u,v\le n\) và \(u\ne v\) là số hiệu trong đồ thị đã xáo trộn. Bộ chấm trả về > nếu cạnh đi từ \(u\) tới \(v\), hoặc < nếu cạnh đi từ \(v\) tới \(u\).

Khi tìm được chu trình, in ! rồi in \(n\) số nguyên \(c_1,c_2,\ldots,c_n\). Các số này phải theo cách đánh số đã xáo trộn. Ngay sau đó, bộ test tiếp theo bắt đầu.

Phải flush standard output sau khi in đồ thị, truy vấn hoặc câu trả lời. Không được đọc hoặc ghi tệp. Khi tương tác kết thúc, chương trình phải thoát bình thường. Tệp đính kèm hamilton-test.py là công cụ thử tương tác chính thức; phần đầu tệp có hướng dẫn sử dụng.

Ràng buộc

• \(4\le n\le500\).
• \(1\le t\le200\).

Cách chấm

Mỗi phân nhóm chỉ có một test input với \(t=200\). Trong từng bộ test, số hiệu các đỉnh được xáo trộn đều ngẫu nhiên. Nếu dùng quá \(10^4\) truy vấn trong một bộ test, bạn nhận Wrong Answer.

Gọi \(Q\) là số truy vấn trung bình trên tất cả bộ test thuộc phân nhóm.

1. \(5\) điểm: \(n=4\), cần \(Q\le12\).
2. \(7\) điểm: \(n=50\), cần \(Q\le1225\).
3. \(12\) điểm: \(n=50\), cần \(Q\le300\).
4. Từ \(1\) đến \(76\) điểm: \(n=500\), cần \(Q\le1500\).

Trong phân nhóm \(4\), số điểm nhận được là

Ví dụ, \(Q=1500\) nhận \(1\) điểm, \(Q=1000\) nhận \(26\) điểm và \(Q=750\) nhận \(76\) điểm.

5 2

01110
00101
00010
01001
10100

? 1 2
>
? 2 3
>
? 3 4
>
? 4 5
>
? 5 1
>
! 1 2 3 4 5

? 1 2
<
? 1 5
>
? 4 3
>
? 4 5
<
? 3 2
>
! 1 5 4 3 2

Nguồn

Baltic Olympiad in Informatics 2026 - đề và dữ liệu chính thức.