Une compagnie de téléphonie mobile propose la promotion suivante : chaque nouveau client peut choisir exactement $k$ autres numéros de téléphone et tous les appels entre le client et l'un quelconque des $k$ contacts choisis sont gratuits (dans les deux sens).
Un groupe de $n$ étudiants (numérotés de $1$ à $n$) souhaite profiter de cette promotion. Chaque étudiant $i$ doit choisir exactement $k$ contacts distincts dans l'ensemble $\{1, 2, \dots, n\} \setminus \{i\}$.
On dit que deux étudiants $i$ et $j$ peuvent se parler gratuitement si au moins l'une des conditions suivantes est vérifiée :
- $i$ a choisi $j$ parmi ses contacts gratuits, ou
- $j$ a choisi $i$ parmi ses contacts gratuits.
Les étudiants veulent choisir leurs contacts gratuits de sorte que n'importe quel étudiant puisse parler gratuitement à n'importe quel autre étudiant, c'est-à-dire que pour chaque paire $(i, j)$ telle que $1 \le i < j \le n$, les étudiants $i$ et $j$ puissent se parler gratuitement.
Pour un $k$ donné, votre tâche consiste à :
- déterminer le nombre maximal possible $n$ d'étudiants pour lequel une telle configuration est possible,
- construire une configuration valide de contacts choisis pour ce $n$ maximal.
Entrée
L'entrée consiste en un seul entier $k$.
Sortie
Sur la première ligne, affichez un seul entier $n$ — le nombre maximal d'étudiants pour lequel il est possible de choisir les contacts gratuits de sorte que deux étudiants quelconques puissent se parler gratuitement.
Sur les $n$ lignes suivantes, affichez les $k$ contacts gratuits choisis par chaque étudiant : sur la ligne $i+1$ (pour $1 \le i \le n$), affichez $k$ entiers distincts $a_{i,1}, a_{i,2}, \dots, a_{i,k}$. Chaque $a_{i,j}$ doit vérifier $1 \le a_{i,j} \le n$ et $a_{i,j} \neq i$. Ces lignes indiquent que l'étudiant $i$ a choisi les étudiants $a_{i,1}, a_{i,2}, \dots, a_{i,k}$ comme contacts gratuits.
S'il existe plusieurs réponses valides, affichez n'importe laquelle d'entre elles.
Contraintes
- $1 \le k \le 1000$.
Exemple 1
2
5
2 5
3 4
1 5
1 3
2 4
Notes
Dans l'exemple, $k = 2$ et le nombre maximal d'étudiants pour lequel il est possible de choisir les contacts gratuits de sorte que deux étudiants quelconques puissent se parler gratuitement est $n = 5$. Pour chaque paire d'étudiants distincts, au moins l'un des deux a choisi l'autre, donc deux étudiants quelconques peuvent se parler gratuitement.