問題文
もちろん、これは問題です。
これはインタラクティブな問題です。頂点数 $n$、辺数 $m$ の未知の無向グラフが与えられます。多重辺や自己ループはありません。あなたは毎回、ジャッジに次の質問をすることができます:
- 頂点集合 $S \subseteq \{1, 2, \dots, n\}$ を指定し、この頂点集合が独立集合であるかどうかを尋ねる。
ここで、独立集合とは、集合 $S$ 内の任意の 2 つの異なる頂点の間に辺が存在しないことを意味します。
あなたの目標は、$M = n + m(2 + \lceil\log_2 n\rceil)$ 回以下の質問を用いて、グラフの辺集合全体を特定することです。
なお、事前に $m$ の値は知らされず、ジャッジは適応的(adaptive)であることに注意してください。すなわち、グラフは最初から固定されているわけではなく、あなたの質問に応じて動的に調整されます。
入力
1 行目には、テストケースの個数を表す整数 $T$ ($1 \le T \le 100$) が与えられます。
各テストケースについて、未知の無向グラフの頂点数を表す整数 $n$ ($1 \le n \le 500$) が 1 行で与えられます。
すべてのテストケースにおける $n$ の総和は $500$ を超えず、$0 \le m \le 500$ であり、$m$ の総和も $500$ を超えないことが保証されます。
入出力
質問を行う際は、次のように 1 行で出力してください:
? k v_1 v_2 ... v_k
ここで、$k$ は頂点集合のサイズを表し、$v_1, v_2, \dots, v_k$ は質問する集合に含まれる頂点の番号であり、互いに異なる必要があります。
ジャッジは整数を 1 つ返します:頂点集合が独立集合であれば $1$、そうでなければ $0$ です。
グラフのすべての辺を特定したら、次のように 1 行で出力してください:
! m u_1 v_1 u_2 v_2 ... u_m v_m
ここで、$m$ は無向グラフの辺数であり、$(u_i, v_i)$ はグラフの辺を表します。辺は任意の順序で出力して構いません。
その後、残りのテストケースがなければプログラムを直ちに終了し、そうでなければ次のテストケースの処理に進んでください。
入力例
入力例 1
1 4 0 1 0 0 1 0
出力例 1
? 2 1 2 ? 2 1 3 ? 2 1 4 ? 2 2 3 ? 2 2 4 ? 2 3 4 ! 4 1 2 2 3 3 4 1 4
入出力例の説明
出力例は、各辺が存在するかどうかを個別に質問する対話プロセスを示しています。