題目描述
給定一個有 $n$ 個頂點嘅有向圖,頂點編號由 $1$ 到 $n$。對於每個頂點 $1 \le i \le n$,頂點 $i$ 嘅出度最多係 $1$;因此我哋可以用一個陣列 $p_i$ 嚟描述呢個圖:如果頂點 $i$ 嘅出度係 $0$,咁 $p_i = 0$;否則 $1 \le p_i \le n$ 且 $p_i \ne i$,代表有一條由 $i$ 指向 $p_i$ 嘅有向邊。圖入面冇有向環,所以由任意頂點 $i$ 出發,沿住有向邊不斷行去下一個頂點所形成嘅路徑,最終都會喺一個出度係 $0$ 嘅頂點停低。
一開始,有一粒木製跳棋擺喺某個頂點上面。當你拍手嗰陣,如果跳棋所在嘅頂點 $i$ 滿足 $p_i$ 非零,佢就會移去頂點 $p_i$;否則佢唔會郁。不過,你完全睇唔到粒跳棋喺邊——你唯一可以做嘅操作係揀一個頂點子集,將跳棋擺喺你揀嘅某個頂點上面,拍手若干次,然後觀察跳棋最後有冇停喺你揀嘅某個頂點上面。連跳棋一開始擺喺邊同埋拍手幾多次都係由交互器決定嘅:你只可以揀頂點子集,然後觀察喺跳棋能夠由你揀嘅某個頂點出發、最後又停喺你揀嘅某個頂點嘅前提下,最多可以拍手幾多次。
你想加一條由 $x$ 去 $y$ 嘅有向邊(滿足 $1 \le x, y \le n$,$x \ne y$,同埋 $p_x = 0$,即係你可以設 $p_x = y$),令到喺成個圖上面可以拍手嘅最大次數多過之前。同時,加咗呢條邊之後圖入面依然唔可以出現任何有向環。
請透過對最多 $n$ 個頂點子集查詢最多可以拍手嘅次數,搵出任意一條可以加嘅邊,或者判斷冇可能加到噉樣嘅邊。
輸入格式
輸入嘅第一行包含一個整數 $n$($1 \le n \le 1000$)。
交互格式
如果要發起一次查詢,請輸出一行形如 $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$ 嘅內容,其中 $1 \le k \le n$,且 $1 \le u_i \le n$ 係你所揀子集入面兩兩唔同嘅頂點。跟住讀入一行,包含一個整數:代表喺跳棋能夠由你揀嘅某個頂點出發、最後停喺你揀嘅某個頂點嘅前提下,最多可以拍手嘅次數。你最多可以進行 $n$ 次查詢。
當你決定好想加邊條邊之後,輸出一行形如 $\texttt{! } x \text{ } y$ 嘅內容,其中 $1 \le x, y \le n$ 係你想加嘅有向邊嘅兩個端點。如果有多過一個解,你可以輸出任意一個。
如果冇可能加到噉樣嘅邊,請輸出 $-1 \text{ -1}$ 嚟代替邊嘅端點。
輸出答案之後,你嘅程式必須即刻終止。
每次發起查詢之後,請刷新輸出緩衝區。
交互器唔係自適應嘅;個圖喺交互開始之前已經固定咗。
範例
6
2
1
2
? 4 1 2 3 4
? 2 5 6
? 3 4 5 6
! 5 1
備註
