game

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 cadru 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 numărul minim de întrebări necesare pentru identificarea ordinii pieselor pe tablă, indiferent care ar fi aceasta.

Date de intrare

În fişierul game.in se va găsi pe prima linie numărul natural nenul $N$.

Date de ieșire

În fişierul game.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 din 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 și precizări

• $1 \leq N \leq 450 \ 000$;

Exemplu

game.in

5

game.out

3
2 3 0
4 3 0
5 0

Explicație

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.