Una compagnia di telefonia mobile offre la seguente promozione: ogni nuovo cliente può scegliere esattamente $k$ altri numeri di telefono e tutte le chiamate tra il cliente e uno qualsiasi dei $k$ contatti scelti sono gratuite (in entrambe le direzioni).
Un gruppo di $n$ studenti (numerati da $1$ a $n$) vuole approfittare di questa promozione. Ogni studente $i$ deve scegliere esattamente $k$ contatti distinti dall'insieme $\{1, 2, \dots, n\} \setminus \{i\}$.
Diciamo che due studenti $i$ e $j$ possono parlare gratis se vale almeno una delle seguenti condizioni:
- $i$ ha scelto $j$ come uno dei contatti gratuiti, oppure
- $j$ ha scelto $i$ come uno dei contatti gratuiti.
Gli studenti vogliono scegliere i propri contatti gratuiti in modo che qualsiasi studente possa parlare gratuitamente con qualsiasi altro studente, cioè per ogni coppia $(i, j)$ con $1 \le i < j \le n$, gli studenti $i$ e $j$ possano parlare gratis.
Per un dato $k$, il tuo compito è:
- determinare il massimo numero possibile $n$ di studenti per cui una tale configurazione è possibile,
- costruire una configurazione valida di contatti scelti per questo $n$ massimo.
Input
L'input è costituito da un singolo intero $k$.
Output
Sulla prima riga, stampa un singolo intero $n$ — il numero massimo di studenti per cui è possibile scegliere i contatti gratuiti in modo che due studenti qualsiasi possano parlare tra loro gratuitamente.
Sulle successive $n$ righe, stampa i $k$ contatti gratuiti scelti da ciascuno studente: sulla riga $i+1$ (per $1 \le i \le n$), stampa $k$ interi distinti $a_{i,1}, a_{i,2}, \dots, a_{i,k}$. Ogni $a_{i,j}$ deve soddisfare $1 \le a_{i,j} \le n$ e $a_{i,j} \neq i$. Queste righe indicano che lo studente $i$ ha scelto gli studenti $a_{i,1}, a_{i,2}, \dots, a_{i,k}$ come propri contatti gratuiti.
Se ci sono più risposte valide, stampane una qualsiasi.
Vincoli
- $1 \le k \le 1000$.
Esempio 1
2
5
2 5
3 4
1 5
1 3
2 4
Note
Nell'esempio, $k = 2$ e il numero massimo di studenti per cui è possibile scegliere i contatti gratuiti in modo che due studenti qualsiasi possano parlare tra loro gratuitamente è $n = 5$. Per ogni coppia di studenti distinti, almeno uno dei due ha scelto l'altro, quindi due studenti qualsiasi possono parlare gratis.