Sebuah perusahaan telepon seluler menawarkan promosi berikut: setiap pelanggan baru dapat memilih tepat $k$ nomor telepon lain dan semua panggilan antara pelanggan tersebut dengan siapa pun dari $k$ kontak yang dipilih adalah gratis (untuk kedua arah).
Sekelompok $n$ siswa (dinomori dari $1$ hingga $n$) ingin memanfaatkan promosi ini. Setiap siswa $i$ harus memilih tepat $k$ kontak berbeda dari himpunan $\{1, 2, \dots, n\} \setminus \{i\}$.
Kita katakan bahwa dua siswa $i$ dan $j$ dapat berbicara secara gratis jika setidaknya salah satu dari hal berikut terpenuhi:
- $i$ telah memilih $j$ sebagai salah satu kontak gratisnya, atau
- $j$ telah memilih $i$ sebagai salah satu kontak gratisnya.
Para siswa ingin memilih kontak gratis mereka sedemikian rupa sehingga setiap siswa dapat berbicara dengan siswa lainnya secara gratis, yaitu untuk setiap pasangan $(i, j)$ dengan $1 \le i < j \le n$, siswa $i$ dan $j$ dapat berbicara secara gratis.
Untuk nilai $k$ yang diberikan, tugas Anda adalah:
- menentukan jumlah maksimum siswa $n$ yang memungkinkan konfigurasi tersebut,
- membentuk satu konfigurasi kontak pilihan yang valid untuk nilai $n$ maksimum ini.
Masukan
Masukan terdiri atas sebuah bilangan bulat $k$.
Keluaran
Pada baris pertama, keluarkan sebuah bilangan bulat $n$ — jumlah maksimum siswa yang memungkinkan pemilihan kontak gratis sehingga setiap dua siswa dapat berbicara satu sama lain secara gratis.
Pada $n$ baris berikutnya, keluarkan $k$ kontak gratis yang dipilih oleh masing-masing siswa: pada baris $i+1$ (untuk $1 \le i \le n$), keluarkan $k$ bilangan bulat berbeda $a_{i,1}, a_{i,2}, \dots, a_{i,k}$. Setiap $a_{i,j}$ harus memenuhi $1 \le a_{i,j} \le n$ dan $a_{i,j} \neq i$. Baris-baris ini menunjukkan bahwa siswa $i$ telah memilih siswa $a_{i,1}, a_{i,2}, \dots, a_{i,k}$ sebagai kontak gratisnya.
Jika terdapat beberapa jawaban yang valid, cetak salah satu di antaranya.
Batasan
- $1 \le k \le 1000$.
Contoh 1
2
5
2 5
3 4
1 5
1 3
2 4
Catatan
Pada contoh, $k = 2$ dan jumlah maksimum siswa yang memungkinkan pemilihan kontak gratis sehingga setiap dua siswa dapat berbicara satu sama lain secara gratis adalah $n = 5$. Untuk setiap pasangan siswa yang berbeda, setidaknya salah satu dari mereka telah memilih yang lain, sehingga setiap dua siswa dapat berbicara secara gratis.