Et mobiltelefonselskap tilbyr følgende kampanje: hver ny kunde kan velge nøyaktig $k$ andre telefonnumre, og alle samtaler mellom kunden og enhver av de $k$ valgte kontaktene er gratis (i begge retninger).
En gruppe på $n$ studenter (nummerert fra $1$ til $n$) ønsker å benytte seg av denne kampanjen. Hver student $i$ må velge nøyaktig $k$ distinkte kontakter fra mengden $\{1, 2, \dots, n\} \setminus \{i\}$.
Vi sier at to studenter $i$ og $j$ kan snakke sammen gratis hvis minst én av følgende gjelder:
- $i$ har valgt $j$ som en av gratis-kontaktene, eller
- $j$ har valgt $i$ som en av gratis-kontaktene.
Studentene ønsker å velge sine gratis-kontakter slik at enhver student kan snakke med enhver annen student gratis, dvs. at for hvert par $(i, j)$ med $1 \le i < j \le n$ kan studentene $i$ og $j$ snakke sammen gratis.
For en gitt $k$ er oppgaven din å:
- bestemme det maksimalt mulige antallet $n$ studenter som en slik konfigurasjon er mulig for,
- konstruere én gyldig konfigurasjon av valgte kontakter for denne maksimale $n$.
Inndata
Inndataene består av et enkelt heltall $k$.
Utdata
På den første linjen skal du skrive ut et enkelt heltall $n$ — det maksimale antallet studenter der det er mulig å velge gratis-kontaktene slik at enhver to studenter kan snakke med hverandre gratis.
På de neste $n$ linjene skal du skrive ut de $k$ gratis-kontaktene valgt av hver student: på linje $i+1$ (for $1 \le i \le n$), skriv ut $k$ distinkte heltall $a_{i,1}, a_{i,2}, \dots, a_{i,k}$. Hver $a_{i,j}$ må tilfredsstille $1 \le a_{i,j} \le n$ og $a_{i,j} \neq i$. Disse linjene angir at student $i$ har valgt studentene $a_{i,1}, a_{i,2}, \dots, a_{i,k}$ som sine gratis-kontakter.
Hvis det finnes flere gyldige svar, kan du skrive ut hvilket som helst av dem.
Begrensninger
- $1 \le k \le 1000$.
Eksempel 1
2
5
2 5
3 4
1 5
1 3
2 4
Merknader
I eksempelet er $k = 2$, og det maksimale antallet studenter der det er mulig å velge gratis-kontaktene slik at enhver to studenter kan snakke med hverandre gratis, er $n = 5$. For hvert par av distinkte studenter har minst én av dem valgt den andre, så enhver to kan snakke sammen gratis.