題目描述
當然,這是一道題。
這是一道互動題。給你一個含有 $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
範例說明
範例展示了逐一詢問每條邊是否存在的互動過程。