Eine Mobilfunkgesellschaft bietet folgende Aktion an: Jeder Neukunde darf genau $k$ andere Telefonnummern auswählen, und alle Gespräche zwischen dem Kunden und jedem der $k$ ausgewählten Kontakte sind (in beide Richtungen) kostenlos.
Eine Gruppe von $n$ Studierenden (nummeriert von $1$ bis $n$) möchte dieses Angebot nutzen. Jeder Studierende $i$ muss genau $k$ verschiedene Kontakte aus der Menge $\{1, 2, \dots, n\} \setminus \{i\}$ auswählen.
Wir sagen, dass zwei Studierende $i$ und $j$ kostenlos miteinander telefonieren können, wenn mindestens eine der folgenden Bedingungen gilt:
- $i$ hat $j$ als einen der kostenlosen Kontakte ausgewählt, oder
- $j$ hat $i$ als einen der kostenlosen Kontakte ausgewählt.
Die Studierenden möchten ihre kostenlosen Kontakte so wählen, dass jeder Studierende mit jedem anderen Studierenden kostenlos telefonieren kann, d. h. für jedes Paar $(i, j)$ mit $1 \le i < j \le n$ können die Studierenden $i$ und $j$ kostenlos telefonieren.
Für ein gegebenes $k$ besteht deine Aufgabe darin:
- die größtmögliche Anzahl $n$ von Studierenden zu bestimmen, für die eine solche Konfiguration möglich ist,
- eine gültige Konfiguration ausgewählter Kontakte für dieses maximale $n$ zu konstruieren.
Eingabe
Die Eingabe besteht aus einer einzigen ganzen Zahl $k$.
Ausgabe
Gib in der ersten Zeile eine einzelne ganze Zahl $n$ aus — die maximale Anzahl von Studierenden, für die es möglich ist, die kostenlosen Kontakte so zu wählen, dass je zwei Studierende kostenlos miteinander telefonieren können.
Gib in den nächsten $n$ Zeilen die $k$ von jedem Studierenden gewählten kostenlosen Kontakte aus: Gib in Zeile $i+1$ (für $1 \le i \le n$) $k$ verschiedene ganze Zahlen $a_{i,1}, a_{i,2}, \dots, a_{i,k}$ aus. Jedes $a_{i,j}$ muss $1 \le a_{i,j} \le n$ und $a_{i,j} \neq i$ erfüllen. Diese Zeilen geben an, dass der Studierende $i$ die Studierenden $a_{i,1}, a_{i,2}, \dots, a_{i,k}$ als kostenlose Kontakte ausgewählt hat.
Falls es mehrere gültige Antworten gibt, gib eine beliebige davon aus.
Bedingungen
- $1 \le k \le 1000$.
Beispiel 1
2
5
2 5
3 4
1 5
1 3
2 4
Hinweise
Im Beispiel ist $k = 2$, und die maximale Anzahl von Studierenden, für die die kostenlosen Kontakte so gewählt werden können, dass je zwei Studierende kostenlos miteinander telefonieren können, beträgt $n = 5$. Für jedes Paar verschiedener Studierender hat mindestens einer den anderen ausgewählt, sodass je zwei kostenlos telefonieren können.