5. Odpad spoločnosti

Obaly od orechovníka, októbrové olovranty, omrvinky od obilných otrúb, odvädnuté obzerance, oreganom ochutená omáčka…

Hrôza. To všetko nájde pani upratovačka v školských laviciach. Každý deň. V jednej triede. Je to na nevydržanie. Ak náhodou stretne nejakého odchádzajúceho študenta a spýta sa ho, čie veci sú v lavici, odpoveď je vždy rovnaká: “Spolusediaceho.” A Janko je fuč. Hlavne, že všetci vychvaľujú, ako čisto majú vo Viedni… a doma si takýto bordel nechajú…

Keďže anonymní spolusediaci sa ťažko obviňujú, rozhodla sa pani upratovačka, že si pekne zistí, kto s kým sedí. Ak náhodou s Jankom sedí Miško, nabudúce mu to poriadne vytmaví. Cez vyučovanie do triedy vojsť nemôže, takže musí vymyslieť iný spôsob ako nájsť dvojice obyvateľov zaprataných lavíc.

Našťastie si pani upratovačka posledných desať rokov zapisuje, koľko lavíc musela vypratávať každý deň. Ak navyše použije záznamy o dochádzke z triednej knihy, nič ju nemôže zastaviť. “Ha ha ha.” Jedine mesiac listovania v zoznamoch… ale na to ste tu vy, dobrosrdeční riešitelia.

Úloha

Táto úloha je interaktívna. Namiesto kompletného vstupu budete dostávať odpovede na vaše otázky.

Pre každú testovaciu sadu dostanete najprv číslo \(n\), udávajúce počet lavíc v triede. Do triedy chodí \(2n\) študentov, číslujeme ich od \(1\) po \(2n\) a v každej lavici sedia práve dvaja. Vašou úlohou je zistiť ktoré dvojice študentov sedia spolu.

Zdrojom vašich informácií sú záznamy o dochádzke a zápisník pani upratovačky. Váš program sa môže spýtať na ľubovoľnú množinu žiakov a zistiť v koľkých laviciach dokopy sedia. (Teda napríklad ak 1 sedí spolu s 2, tak \(\{1, 2\}\) sedia v jednej lavici, \(\{1,3\}\) sedia v dvoch laviciach a \(\{1,2,3\}\) sedia tiež v dvoch laviciach.)

Môžete sa však spýtať najviac \(20\,000\) otázok.

Formát vstupu

Na prvom riadku vstupu je malé kladné celé číslo \(t\) udávajúce počet sád.

Pre každú sadu dostanete na novom riadku kladné celé číslo \(n\) neprevyšujúce \(1\,000\), určujúce počet lavíc v triede.

Následne testovač odpovedá na každú vašu otázku vypísaním jedného celého čísla na nový riadok – počet lavíc, v ktorých títo žiaci sedia. Túto odpoveď viete načítať zo štandartného vstupu.

Formát výstupu

Na počet lavíc, v ktorých sedí \(m\) študentov sa spýtate vypísaním čísla \(m\) a následne vypíšte čísla študentov \(s_1, s_2, ..., s_m\), o ktorých sa zaujímate do jedného riadku oddelených medzerami. Aby bola vaša otázka spracovaná potrebujete výstup presunúť z pamäte na štandartný výstup pomocou príkazu fflush(stdout); v C++, alebo flush(output); v Pascale.

Keď ste si istí, že poznáte všetky dvojice, vypíšte \(0\) na nový riadok a \(n\) riadkov dvojíc čísel študentov, ktorí sedia spolu.

Pokiaľ sa spýtate viac ako \(20\,000\) otázok, váš program bude nemilostrdne ukončený, avšak v testovači sa to môže prejaviť rôzne. Odpovede “prekročený časový limit”, “chyba počas vykonávania programu” aj “zlá odpoveď” môžu ale nemusia v skutočnosti zmanenať, že ste sa opýtali priveľa otázok.

Príklad

Input:

2       // počet sád
3       // počet lavíc v prvej sade
2
1
2
2
2       // počet lavíc v druhej sade
1

Output:

3 1 2 3
2 1 2
2 3 4
2 3 5
0
1 2
3 6
4 5
2 1 2
0
1 2
4 3

Skutočné vstupy neobsahujú “//” ani text za týmito znakmi. Pridali sme ich do ukážkového vstupu kvóli prehľadnosti.

Najprv sa dozvieme, že študenti \(1, 2, 3\) obsadzujú 2 lavice. Zistíme, že \(1, 2\) sedia spolu. Treťou a štvrtou otázkou zistíme, že študent \(3\) nesedí so \(4\) ani s Peťkou, teda musí sedieť so spolužiakom \(6\). Zvyšní dvaja študenti, \(4, 5\) musia teda sedieť spolu.

V druhej sade sa spýtame na dvojicu \(1, 2\). Keď sa dozvieme, že sedia spolu, už je zjavné, ako trieda vyzerá.