Diese Aufgabe ist interaktiv.
Wir haben einen ungerichteten Graphen $G$ mit $n$ Knoten vor dir verborgen. Es ist garantiert, dass er zusammenhängend ist und weder Mehrfachkanten noch Schleifen enthält.
Du darfst bis zu 60 Anfragen der folgenden Form stellen:
- Betrachte eine Teilmenge $S$ der Knotenmenge von $G$. Wie viele Kanten gibt es in dem von $S$ induzierten Teilgraphen? Anders ausgedrückt: Wie viele Kanten in $G$ haben beide Endpunkte in $S$?
Dein Ziel ist festzustellen, ob es in diesem Graphen einen Eulerkreis gibt. Ein Eulerkreis ist ein Weg im Graphen, der jede Kante genau einmal durchläuft und am selben Knoten beginnt und endet.
Beachte, dass der Graph $G$ vor Beginn der Interaktion festgelegt wird. Der Interaktor ist also nicht adaptiv.
Eingabe
Die erste Zeile enthält eine ganze Zahl $n$ ($3 \le n \le 10^4$), die Anzahl der Knoten in $G$. Es ist garantiert, dass $G$ höchstens $10^5$ Kanten hat, zusammenhängend ist und weder Mehrfachkanten noch Schleifen enthält.
Interaktion
Beginne die Interaktion, indem du eine Zeile mit der ganzen Zahl $n$ einliest.
Um die Anzahl der Kanten im von $k$ Knoten $x_1,x_2,\ldots,x_k$ induzierten Teilgraphen von $G$ zu ermitteln, gib eine Zeile im Format ? k x1 x2 ... xk aus ($0 \le k \le n$, $1 \le x_i \le n$, alle $x_i$ sind verschieden).
Als Antwort gibt das Juryprogramm eine Zeile mit einer ganzen Zahl $m$ aus: der Anzahl solcher Kanten.
Falls deine Anfrage ungültig ist oder du mehr als 60 Anfragen gestellt hast, gibt das Juryprogramm $-1$ aus und beendet die Interaktion. Du erhältst das Ergebnis „Falsche Antwort“. Beende deine Lösung sofort, um andere Ergebnisse zu vermeiden.
Sobald du festgestellt hast, ob der Graph einen Eulerkreis enthält, gib eine einzelne Zeile aus: ! YES, falls ein solcher Kreis existiert, und ! NO, falls nicht.
Vergiss nach jeder ausgegebenen Zeile nicht den Zeilenumbruch und das Leeren des Ausgabepuffers. Andernfalls erhältst du das Ergebnis „Inaktivitätslimit überschritten“.
Beispiele
Eingabe 1
3 1 0
Ausgabe 1
? 2 1 2 ? 2 1 3 ! NO
Hinweis
Der verborgene Graph im Beispiel hat $3$ Knoten und die Kanten $(2,1)$ und $(2,3)$.