Matkapuhelinyhtiö tarjoaa seuraavan kampanjan: jokainen uusi asiakas saa valita täsmälleen $k$ muuta puhelinnumeroa, ja kaikki puhelut asiakkaan ja kenen tahansa $k$ valitun yhteyshenkilön välillä ovat ilmaisia (molempiin suuntiin).
$n$ opiskelijan ryhmä (numeroitu $1$:stä $n$:ään) haluaa hyödyntää tätä kampanjaa. Jokaisen opiskelijan $i$ täytyy valita täsmälleen $k$ eri yhteyshenkilöä joukosta $\{1, 2, \dots, n\} \setminus \{i\}$.
Sanomme, että kaksi opiskelijaa $i$ ja $j$ voivat puhua ilmaiseksi, jos vähintään toinen seuraavista pätee:
- $i$ on valinnut $j$:n yhdeksi ilmaisista yhteyshenkilöistään, tai
- $j$ on valinnut $i$:n yhdeksi ilmaisista yhteyshenkilöistään.
Opiskelijat haluavat valita ilmaiset yhteyshenkilönsä niin, että kuka tahansa opiskelija voi puhua kenen tahansa muun opiskelijan kanssa ilmaiseksi, eli jokaiselle parille $(i, j)$, jolle $1 \le i < j \le n$, opiskelijat $i$ ja $j$ voivat puhua ilmaiseksi.
Annetulle $k$:lle tehtäväsi on:
- määrittää suurin mahdollinen opiskelijoiden lukumäärä $n$, jolle tällainen asetelma on mahdollinen,
- muodostaa yksi kelvollinen valittujen yhteyshenkilöiden asetelma tälle suurimmalle $n$:lle.
Syöte
Syöte koostuu yhdestä kokonaisluvusta $k$.
Tuloste
Tulosta ensimmäiselle riville yksi kokonaisluku $n$ — suurin opiskelijoiden lukumäärä, jolle on mahdollista valita ilmaiset yhteyshenkilöt niin, että ketkä tahansa kaksi opiskelijaa voivat puhua keskenään ilmaiseksi.
Tulosta seuraaville $n$ riville kunkin opiskelijan valitsemat $k$ ilmaista yhteyshenkilöä: riville $i+1$ (kun $1 \le i \le n$) tulosta $k$ erisuurta kokonaislukua $a_{i,1}, a_{i,2}, \dots, a_{i,k}$. Jokaisen $a_{i,j}$ on toteutettava ehdot $1 \le a_{i,j} \le n$ ja $a_{i,j} \neq i$. Nämä rivit ilmaisevat, että opiskelija $i$ on valinnut opiskelijat $a_{i,1}, a_{i,2}, \dots, a_{i,k}$ ilmaisiksi yhteyshenkilöikseen.
Jos kelvollisia vastauksia on useita, tulosta mikä tahansa niistä.
Rajoitukset
- $1 \le k \le 1000$.
Esimerkki 1
2
5
2 5
3 4
1 5
1 3
2 4
Huomautukset
Esimerkissä $k = 2$ ja suurin opiskelijoiden lukumäärä, jolle ilmaiset yhteyshenkilöt voidaan valita niin, että ketkä tahansa kaksi opiskelijaa voivat puhua keskenään ilmaiseksi, on $n = 5$. Jokaiselle eri opiskelijoiden parille vähintään toinen on valinnut toisen, joten ketkä tahansa kaksi voivat puhua ilmaiseksi.