Có một đồ thị vô hướng đơn với $n$ đỉnh. Đồ thị này có một tính chất bổ sung:

• Mọi đồ thị con cảm sinh đều chứa một đỉnh có bậc tối đa là $k$.

Bạn cần tìm đồ thị ẩn này. Bạn có thể kiểm tra xem bất kỳ tập con nào có phải là tập độc lập hay không. Nếu không, chúng tôi sẽ chỉ cho bạn một cạnh có cả hai đầu mút nằm trong tập hợp đó.

Chúng tôi sẽ không thay đổi đồ thị trong quá trình tương tác, vì vậy bạn có thể giả định rằng nó là cố định. Tuy nhiên, chúng tôi có thể chọn bất kỳ cạnh nào bên trong đồ thị con cảm sinh để hiển thị. Nói cách khác, trong tất cả các bài kiểm tra, đồ thị là cố định, nhưng bộ tương tác là thích nghi.

Bạn cần đoán đồ thị trong tối đa $2nk + n$ truy vấn.

Giao thức tương tác

Quá trình tương tác bắt đầu với một dòng chứa một số nguyên $n$: số lượng đỉnh trong đồ thị ẩn ($2 \le n \le 2000$).

Số nguyên $k$ không được cho trước, nhưng nó thỏa mãn điều kiện $1 \le k < n$ và $nk \le 2000$.

Sau đó, bạn có thể thực hiện các truy vấn.

Để thực hiện một truy vấn, hãy in một dòng chứa "? $k$" ($1 \le k \le n$) và sau đó là $k$ số nguyên phân biệt $v_1, v_2, \dots, v_k$ ($1 \le v_i \le n$). Phân cách các số nguyên liên tiếp bằng dấu cách. Sau đó, hãy xóa bộ đệm đầu ra (flush).

Sau mỗi truy vấn, hãy đọc một dòng với hai số nguyên $i, j$. Nếu không có cạnh nào trong đồ thị con cảm sinh $v_1, v_2, \dots, v_k$, thì $i = j = -1$. Ngược lại, $i \neq j$, $i \in v, j \in v$, và có một cạnh nối hai đầu mút $i$ và $j$ trong đồ thị.

Khi bạn tìm thấy đồ thị, ở dòng đầu tiên, hãy in một dòng chứa "! $m$". Sau đó, $m$ dòng tiếp theo sẽ chứa mô tả các cạnh của đồ thị, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le n$), biểu thị chỉ số của các đỉnh được nối với nhau bởi một cạnh.

Giải pháp của bạn sẽ nhận kết quả Wrong Answer hoặc Time Limit Exceeded nếu bạn thực hiện nhiều hơn $2nk + n$ truy vấn.

Giải pháp của bạn sẽ nhận kết quả Idleness Limit Exceeded nếu bạn không in bất cứ thứ gì hoặc quên xóa bộ đệm đầu ra.

Để xóa bộ đệm (flush), bạn cần thực hiện ngay sau khi in một truy vấn và một dòng mới:

• fflush(stdout) hoặc cout.flush() trong C++;
• System.out.flush() trong Java;
• flush(output) trong Pascal;
• stdout.flush() trong Python;
• Xem tài liệu cho các ngôn ngữ khác.

Ví dụ

Dữ liệu vào 1

3
-1 -1
-1 -1
1 2

Dữ liệu ra 1

? 2 1 2
? 2 2 3
? 2 1 3
! 3
1 2
2 3
1 3