Problembeskrivelse
Selvfølgelig er dette et problem.
Dette er et interaktivt problem. Du får gitt en ukjent urettet graf med $n$ noder og $m$ kanter, uten multikanter eller løkker. Hver gang kan du stille interaksjonsbiblioteket følgende spørsmål:
- Gitt en nodemengde $S \subseteq \{1, 2, \dots, n\}$, spør om denne nodemengden er en uavhengig mengde.
Her betyr en uavhengig mengde at det ikke er noen kant mellom noen to forskjellige noder i mengden $S$.
Målet ditt er å bestemme hele kantmengden til grafen ved å bruke høyst $M = n + m(2 + \lceil\log_2 n\rceil)$ spørringer.
Merk at du ikke kjenner verdien av $m$ på forhånd, og at interaksjonsbiblioteket er adaptivt, dvs. at grafen ikke er fastsatt fra starten av, men justeres dynamisk i henhold til spørringene dine.
Inndata
Den første linjen inneholder et heltall $T$ ($1 \le T \le 100$), som angir antall testtilfeller.
For hvert testtilfelle inneholder én linje et heltall $n$ ($1 \le n \le 500$), som angir antall noder i den ukjente urettede grafen.
Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $500$, $0 \le m \le 500$, og at summen av $m$ ikke overstiger $500$.
Interaksjon
Når du trenger å stille en spørring, skriv ut én linje:
? k v_1 v_2 ... v_k
der $k$ angir størrelsen på nodemengden, og $v_1, v_2, \dots, v_k$ er indeksene til nodene i mengden du spør om, alle parvis forskjellige.
Interaksjonsbiblioteket vil returnere et heltall: $1$ hvis nodemengden er en uavhengig mengde; $0$ ellers.
Når du har bestemt alle kantene i grafen, skriv ut én linje:
! m u_1 v_1 u_2 v_2 ... u_m v_m
der $m$ er antall kanter i den urettede grafen, og $(u_i, v_i)$ representerer en kant i grafen. Du kan skrive ut kantene i hvilken som helst rekkefølge.
Etter det, hvis det ikke er flere testtilfeller igjen, må programmet ditt avsluttes umiddelbart; ellers skal det gå videre til neste testtilfelle.
Eksempler
Inndata 1
1 4 0 1 0 0 1 0
Utdata 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
Merk
Eksempelet viser en interaktiv prosess der man spør individuelt om hver kant eksisterer.