Đây là bài toán tương tác.

Biển ơi, lại gặp nhau rồi. Mong kỳ nghỉ hè năm sau cũng hạnh phúc!

Rất lâu trước đây, Una và Kamome đã là bạn tốt. Họ thích chơi trò chơi. Lần trước, trò chơi do Una phát minh đã được Kamome giải quyết dễ dàng nhờ chiến lược xuất sắc. Lần này, Una mang đến một trò chơi mới.

Una đang nghĩ về một cây có $n$ đỉnh. Kamome có thể thực hiện tối đa $n$ truy vấn:

• Kamome có thể đưa cho Una một hoán vị $P_1, P_2, \dots, P_n$ (với $0 \le P_i \le n-1$ và tất cả $P_i$ đôi một khác nhau). Sau đó Una sẽ cho Kamome biết độ dài đường kính có trọng số của cây khi gán trọng số $2^{P_i}$ cho đỉnh $i$.

Nhưng đôi khi Kamome nhận ra rằng Una đang gây rối. Cụ thể hơn, có những trường hợp dù hỏi bao nhiêu lần cũng không thể xác định chắc chắn cây. Trong trường hợp đó, Kamome có thể báo rằng không có lời giải.

Giao tiếp

Đây là bài toán tương tác. Sau mỗi lần xuất, bạn phải xóa bộ đệm đầu ra. Để xóa bộ đệm, bạn có thể dùng:

• C/C++: fflush(stdout) hoặc cout.flush()
• Java và Kotlin: System.out.flush()
• Python: sys.stdout.flush()

Đầu tiên, bạn cần đọc số lượng test case $T$ ($1 < T < 10^4$). Với mỗi test case, đọc kích thước cây $n$ ($2 \le n \le 100$, $\sum n^2 < 10^6$).

Để thực hiện truy vấn, hãy xuất một dòng có dạng "? $P_1 P_2 \dots P_n$" (với $0 \le P_i \le n-1$ và $P_i \ne P_j$ khi $1 < i < j \le n$). Sau đó, đọc một xâu gồm $n$ ký tự biểu diễn trọng số đường kính của cây ở dạng nhị phân. Nếu truy vấn không hợp lệ hoặc bạn thực hiện nhiều hơn $n$ truy vấn trong một test case, chương trình chấm sẽ xuất ra -1. Nếu đọc được -1, bạn phải kết thúc ngay lập tức để tránh hành vi không xác định.

Nếu cho rằng không thể xác định duy nhất cây, hãy xuất "! NO". Ngược lại, hãy xuất một dòng có dạng "! YES $u_1 v_1 u_2 v_2 \dots u_{n-1} v_{n-1}$" biểu thị cây có các cạnh $(u_i, v_i)$. Các cạnh có thể được xuất theo bất kỳ thứ tự nào.

Sau đó, đọc một từ "OK" hoặc "WA" cho biết đáp án có đúng hay không. Nếu đọc được "WA", bạn phải kết thúc ngay lập tức để tránh hành vi không xác định. Nếu bạn xuất YES dù cây không thể xác định, dù câu trả lời có đúng, Una sẽ nghĩ bạn đang gian lận và câu trả lời sẽ bị coi là sai.

Chương trình chấm không phải là thích ứng, vì vậy câu trả lời không thay đổi sau các truy vấn.

Ví dụ

Dữ liệu vào 1

2
4
1110
1110
OK
3
111
OK

Dữ liệu ra 1

? 0 1 2 3
? 2 1 0 3
! YES 1 4 2 4 3 4
? 0 1 2
! NO

Ghi chú

Công cụ kiểm tra được cung cấp để thí sinh phát triển và kiểm tra lời giải. Công cụ này có thể tải xuống từ tệp đính kèm. Chạy công cụ với tùy chọn "-h" sẽ giải thích cách sử dụng. Công cụ kiểm tra chỉ thực hiện một số chức năng của trình chấm thực tế và chỉ thực hiện một số kịch bản kiểm tra.