Ionică şi Gigel joacă un joc cu N piese numerotate de la 1 la N, care se aşează într-o ordine oarecare pe o tăbliţă, sub forma unui şir. Gigel aşează piesele pe tăbliţă iar Ionică trebuie să ghicească ordinea lor din cât mai puţine întrebări. În cadrul unei întrebări Ionică precizează un număr oarecare de poziţii de pe tablă, unde vrea să cunoască ce piese se află. Ionică va răspunde specificând care este mulţimea valorilor plasate pe acele poziţii, dar nu va preciza pentru fiecare poziţie ce valoare îi corespunde. Poziţiile tablei sunt numerotate de la 1 la N.
Cerinţă
Cunoscându-se numărul N de piese, să se determine o secvenţă cu număr minim de întrebări, necesare pentru identificarea ordinii pieselor pe tablă, indiferent care ar fi aceasta.
Date de intrare
În fişierul game1.in se va găsi pe prima linie numărul natural nenul N.
Date de ieşire
În fişierul game1.out se va scrie pe prima linie un număr K reprezentând numărul minim de întrebări determinat. Următoarele K linii din fişier codifică întrebările. Fiecare întrebare conţine un şir de numere naturale distincte, reprezentând poziţiile vizate în cadrul întrebării curente. Fiecare dintre aceste K linii se termină cu valoarea 0. Numerele în cadrul unei linii sunt separate prin câte un spaţiu.
Problema admite mai multe soluţii. În fişierul de ieşire nu contează ordinea de scriere a poziţiilor în cadrul unei întrebări.
Restricţii
0 < N <= 450000
Exemple
game1.in
game1.out
Explicaţii
5
3
2 3 0
4 3 0
5 0
Prima şi a doua întrebare determină sigur valoarea piesei de pe poziţia 3.
Ştiind această valoare şi răspunsul la prima întrebare se poate stabili exact care este piesa de pe poziţia 2.
Analog pe baza răspunsului la întrebarea a doua se poate determina valoarea piesei de pe poziţia 4.
După primele două întrebări rămân indecise piesele de pe prima şi ultima poziţie.
Ultima întrebare stabileşte valoarea piesei situate pe poziţia 5, deci implicit se poate determina şi valoarea piesei de pe prima poziţie.