Mô tả
Có một đồ thị có hướng gồm $n$ đỉnh được đánh số từ $1$ đến $n$. Với mỗi đỉnh $1 \le i \le n$, bậc ra của đỉnh $i$ nhiều nhất là một; do đó ta có thể mô tả đồ thị bằng một mảng $p_i$, trong đó $p_i = 0$ nếu bậc ra của đỉnh $i$ bằng không, và ngược lại $1 \le p_i \le n$, $p_i \ne i$, đồng thời có một cạnh có hướng từ $i$ đến $p_i$. Không có chu trình có hướng nào trong đồ thị, vì vậy từ bất kỳ đỉnh $i$ nào, đường đi tạo bởi việc liên tục di chuyển sang đỉnh tiếp theo dọc theo các cạnh có hướng cuối cùng sẽ kết thúc tại một đỉnh có bậc ra bằng không.
Ban đầu, có một quân cờ bằng gỗ nằm trên một trong các đỉnh. Khi bạn vỗ tay, nếu quân cờ đang ở một đỉnh $i$ có $p_i$ khác không, nó sẽ di chuyển đến đỉnh $p_i$; ngược lại nó đứng yên. Tuy nhiên, bạn hoàn toàn không thể nhìn thấy quân cờ đang ở đâu — thao tác duy nhất bạn có thể thực hiện là chọn một tập con các đỉnh, đặt quân cờ lên một trong các đỉnh đã chọn, vỗ tay một số lần, và quan sát xem liệu quân cờ có kết thúc tại một trong các đỉnh bạn đã chọn hay không. Thậm chí vị trí đặt quân cờ ban đầu và số lần bạn vỗ tay cũng do trình tương tác chọn: bạn chỉ được chọn tập con các đỉnh, và quan sát số lần tối đa bạn có thể vỗ tay sao cho quân cờ có thể bắt đầu ở một trong các đỉnh đã chọn và kết thúc ở một trong các đỉnh đã chọn.
Bạn muốn thêm một cạnh duy nhất từ $x$ đến $y$ ($1 \le x, y \le n$, $x \ne y$, và $p_x = 0$, tức là bạn có thể gán $p_x = y$), sao cho bạn có thể vỗ tay nhiều lần hơn trước trên toàn bộ đồ thị. Tuy nhiên, việc thêm cạnh này không được tạo ra bất kỳ chu trình có hướng nào trong đồ thị.
Hãy tìm một cạnh bất kỳ như vậy mà bạn có thể thêm bằng cách truy vấn số lần vỗ tay tối đa trên nhiều nhất $n$ tập con các đỉnh, hoặc xác định rằng không thể thêm một cạnh như vậy.
Dữ liệu vào
Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $n$ ($1 \le n \le 1000$).
Tương tác
Để thực hiện một truy vấn, hãy in ra một dòng có dạng $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$, trong đó $1 \le k \le n$, và $1 \le u_i \le n$ là các đỉnh đôi một phân biệt trong tập con bạn chọn. Sau đó đọc một dòng chứa một số nguyên duy nhất: số lần tối đa bạn có thể vỗ tay sao cho quân cờ có thể bắt đầu ở một trong các đỉnh đã chọn và kết thúc ở một trong các đỉnh đã chọn. Bạn được thực hiện nhiều nhất $n$ truy vấn.
Sau khi đã xác định được cạnh muốn thêm, hãy in ra một dòng có dạng $\texttt{! } x \text{ } y$, trong đó $1 \le x, y \le n$ là hai đầu mút của cạnh có hướng bạn muốn thêm. Nếu có nhiều đáp án, bạn có thể in ra bất kỳ đáp án nào.
Nếu không thể thêm được cạnh như vậy, hãy in ra $-1 \text{ -1}$ thay vì hai đầu mút của cạnh.
Chương trình của bạn phải kết thúc ngay lập tức sau khi in ra đáp án.
Hãy xóa bộ đệm xuất (flush) sau mỗi truy vấn bạn thực hiện.
Trình tương tác không thích ứng (non-adaptive); đồ thị đã được cố định trước.
Ví dụ
6
2
1
2
? 4 1 2 3 4
? 2 5 6
? 3 4 5 6
! 5 1
Ghi chú
