Problembeschreibung
Natürlich ist das ein Problem.
Dies ist ein interaktives Problem. Gegeben ist ein unbekannter ungerichteter Graph mit $n$ Knoten und $m$ Kanten, ohne Mehrfachkanten oder Selbstschleifen. Jedes Mal kannst du der Interaktionsbibliothek die folgende Frage stellen:
- Gegeben eine Knotenmenge $S \subseteq \{1, 2, \dots, n\}$, frage, ob diese Knotenmenge eine unabhängige Menge ist.
Hierbei bedeutet eine unabhängige Menge, dass es zwischen je zwei verschiedenen Knoten in der Menge $S$ keine Kante gibt.
Dein Ziel ist es, die gesamte Kantenmenge des Graphen mit höchstens $M = n + m(2 + \lceil\log_2 n\rceil)$ Abfragen zu bestimmen.
Beachte, dass du den Wert von $m$ im Voraus nicht kennst und die Interaktionsbibliothek adaptiv ist, d. h. der Graph steht nicht von Anfang an fest, sondern wird dynamisch entsprechend deinen Abfragen angepasst.
Eingabe
Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 100$), die die Anzahl der Testfälle angibt.
Für jeden Testfall enthält eine Zeile eine ganze Zahl $n$ ($1 \le n \le 500$), die die Anzahl der Knoten des unbekannten ungerichteten Graphen angibt.
Es wird garantiert, dass die Summe von $n$ über alle Testfälle $500$ nicht überschreitet, $0 \le m \le 500$ gilt und die Summe von $m$ ebenfalls $500$ nicht überschreitet.
Interaktion
Wenn du eine Abfrage stellen möchtest, gib eine Zeile aus:
? k v_1 v_2 ... v_k
wobei $k$ die Größe der Knotenmenge bezeichnet und $v_1, v_2, \dots, v_k$ die Indizes der Knoten in der abgefragten Menge sind, alle paarweise verschieden.
Die Interaktionsbibliothek gibt eine ganze Zahl zurück: $1$, falls die Knotenmenge eine unabhängige Menge ist; andernfalls $0$.
Wenn du alle Kanten des Graphen bestimmt hast, gib eine Zeile aus:
! m u_1 v_1 u_2 v_2 ... u_m v_m
wobei $m$ die Anzahl der Kanten im ungerichteten Graphen ist und $(u_i, v_i)$ eine Kante im Graphen darstellt. Du kannst die Kanten in beliebiger Reihenfolge ausgeben.
Wenn danach keine weiteren Testfälle übrig sind, muss dein Programm sofort beendet werden; andernfalls sollte es mit dem nächsten Testfall fortfahren.
Beispiele
Eingabe 1
1 4 0 1 0 0 1 0
Ausgabe 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
Hinweis
Das Beispiel zeigt einen interaktiven Prozess, bei dem einzeln abgefragt wird, ob jede Kante existiert.