題目描述
當然,呢個係一道題。
呢個係一道交互題。俾你一個有 $n$ 個頂點同 $m$ 條邊嘅未知無向圖,圖入面冇重邊或者自環。每次你可以向交互庫問以下問題:
- 俾定一個頂點集合 $S \subseteq \{1, 2, \dots, n\}$,詢問呢個頂點集合係咪一個獨立集。
喺度,獨立集嘅意思係集合 $S$ 入面任意兩個唔同頂點之間都冇邊相連。
你嘅目標係用唔超過 $M = n + m(2 + \lceil\log_2 n\rceil)$ 次詢問嚟確定成張圖嘅所有邊。
請注意,你事先並唔知道 $m$ 嘅值,而且交互庫係自適應(adaptive)嘅,即係張圖喺一開始並唔係固定嘅,而係會根據你嘅詢問動態調整。
輸入格式
第一行包含一個整數 $T$ ($1 \le T \le 100$),表示測試數據嘅組數。
對於每組測試數據,一行包含一個整數 $n$ ($1 \le n \le 500$),表示呢張未知無向圖嘅頂點數。
保證所有測試數據入面 $n$ 嘅總和唔超過 $500$,$0 \le m \le 500$,而且 $m$ 嘅總和唔超過 $500$。
交互格式
當你需要進行詢問時,輸出一行:
? k v_1 v_2 ... v_k
其中 $k$ 表示頂點集合嘅大細,$v_1, v_2, \dots, v_k$ 係你所詢問嘅集合入面嘅頂點編號,佢哋兩兩唔同。
交互庫會返回一個整數:如果呢個頂點集合係獨立集,就返回 $1$;否則返回 $0$。
當你確定咗圖入面嘅所有邊時,輸出一行:
! 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
範例解釋
範例展示咗逐條邊詢問是否存在嘅交互過程。