Opis problemu
Oczywiście, że to jest zadanie.
To jest zadanie interaktywne. Dany jest nieznany graf nieskierowany o $n$ wierzchołkach i $m$ krawędziach, bez krawędzi wielokrotnych ani pętli własnych. Za każdym razem możesz zadać bibliotece interakcji następujące pytanie:
- Mając dany zbiór wierzchołków $S \subseteq \{1, 2, \dots, n\}$, zapytaj, czy ten zbiór wierzchołków jest zbiorem niezależnym.
Tutaj zbiór niezależny oznacza, że pomiędzy żadnymi dwoma różnymi wierzchołkami w zbiorze $S$ nie ma krawędzi.
Twoim celem jest wyznaczenie całego zbioru krawędzi grafu przy użyciu co najwyżej $M = n + m(2 + \lceil\log_2 n\rceil)$ zapytań.
Zauważ, że wartość $m$ nie jest znana z góry, a biblioteka interakcji jest adaptacyjna, tj. graf nie jest ustalony od samego początku, lecz będzie dynamicznie dostosowywany w zależności od Twoich zapytań.
Wejście
Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 100$), oznaczającą liczbę przypadków testowych.
Dla każdego przypadku testowego jeden wiersz zawiera liczbę całkowitą $n$ ($1 \le n \le 500$), oznaczającą liczbę wierzchołków nieznanego grafu nieskierowanego.
Gwarantowane jest, że suma $n$ po wszystkich przypadkach testowych nie przekracza $500$, $0 \le m \le 500$, a suma $m$ nie przekracza $500$.
Interakcja
Gdy chcesz zadać zapytanie, wypisz jeden wiersz:
? k v_1 v_2 ... v_k
gdzie $k$ oznacza rozmiar zbioru wierzchołków, a $v_1, v_2, \dots, v_k$ to indeksy wierzchołków w zbiorze, o który pytasz, wszystkie parami różne.
Biblioteka interakcji zwróci liczbę całkowitą: $1$, jeśli zbiór wierzchołków jest zbiorem niezależnym; $0$ w przeciwnym razie.
Gdy wyznaczysz już wszystkie krawędzie grafu, wypisz jeden wiersz:
! m u_1 v_1 u_2 v_2 ... u_m v_m
gdzie $m$ jest liczbą krawędzi w grafie nieskierowanym, a $(u_i, v_i)$ reprezentuje krawędź w grafie. Krawędzie możesz wypisać w dowolnej kolejności.
Następnie, jeśli nie ma już więcej przypadków testowych, Twój program musi natychmiast zakończyć działanie; w przeciwnym razie powinien przejść do kolejnego przypadku testowego.
Przykłady
Wejście 1
1 4 0 1 0 0 1 0
Wyjście 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
Uwaga
Przykład przedstawia proces interakcji polegający na odpytywaniu o istnienie każdej krawędzi z osobna.